There isn't one definitive answer to this question besides "Try to be Paul McCartney." That said, here are some guidelines that I hope prove helpful:
Mix It Up
Don't just use chord tones (meaning, notes that are in the chord you're playing at the moment) and don't just use non-chord tones. Non-chord tones will give your melody a sense of momentum and tension, while chord tones will give your melody a sense of stability and release. Of the chord tones, roots and fifths have the most stability, while thirds and sevenths strike a nice balance. Too much of either is no good: too much tension and momentum, and you run the risk of your melody running out of control, which ultimately feels chaotic. Too much stability, and your melody will sound dull and boring.
Voice Leading
This basically means that your melody shouldn't jump around too much---a few big intervals are fine and can be really dramatic, but most of the time, your melody should stick to stringing together notes that are near each other. Otherwise it's hard for the listener's ear to keep up.
For example, say you're playing the A-D-E chord progression you mentioned. C# is the third of the A chord, and D is the root of the D chord (obviously). So a melody that plays the C# and then the D is employing voice leading.
Choosing Chords
So you have the opposite challenge: to pick chords to fit a melody. As before, there's no one right way to go about this, but again, here are some guidelines:
- Identify the notes in the melody that feel more stable as opposed to those that feel as though they have momentum and movement and use those to help inform your chord choices.
- Identify the few notes with the most drama. These probably shouldn't be chord tones, but might resolve to chord tones.
- Chord progressions have their own momentum and stability. I chords are stable; V chords have momentum. You resolve a V (or V7) chord to its corresponding I chord. Unless you absolutely know what you're doing, make sure your V chords resolve or the song will leave your listeners feeling unsettled.
Example: "Eleanor Rigby"
"Eleanor Rigby"---"Rig" and "by" are both chord tones, and the melody lands on "by" like a rock. That note is the root of the chord, and it provides a lot of stability for the melody, which is good because the next line is...
"Picks up the rice in a church where a wedding has been"---"Rice" and "church" aren't chord tones, and they have a lot of momentum. This line is almost like a roller coaster: "Picks up the" is the initial ascent, followed by a briefly held point of tension on "rice", then a quick fall, a quick rise, and then another briefly held point of tension on "church", another fall, etc. It ends on "been", which is a chord tone for the next chord (the IV chord). Stability and release after the tension and drama of the roller coaster. Paul knew what he was doing.
I could go on, but it would take a long time, and this the main idea. Good luck, and enjoy the adventure of composition!