Hi ON2004
What genre are you playing around with?
I have played around in music production software, and it might be the easiest way of trying out melodies over chords. FL studio is pretty straight forward.
IMO its all about creating the right feeling by using both rhythm and the outlining and/or emphasizing of certain chords and/or notes. Building vs releasing tension. Building vs slowing down momentum. Creating and reducing space. Certainty vs uncertainty etc etc.. Many different ways of looking at it.
It might be worth looking at how the different modes can create different "feels" and then playing accordingly. You should be able to find a YouTube video or two on this subject. Also go take a look at how different intervals affect the feel of a progression.
What helped me quite a bit was listening to songs of bands that influenced me a lot that contained the same effect that I wanted to achieve and actually diving into how the melodies was playing off of the chords (are they using a lot of 3rd or 7th notes? Is the tempo on a constant high or does it fluctuate between different parts and how? Key changes? What beats are emphasized? etc. etc.).
Don't get stuck into only trying to listen for other guitars, listen what the other instruments are also doing over the chord progression, I especially like to listen to what a string section does, and the drums will give you a great idea on what to emphasize.
One of my favorite bands to listen to in this regard is The National. Most of what they do is so simple, but everything they add and take away makes a massive difference to a song.
The song "Slow Show" for example has a rhythm guitar, fast strumming pattern and "light" minor chords that resolves to a major, making it almost a lighthearted but kinda sad feel. An Ambient guitar can be heard in the background adding almost an eerie feel in the silent parts, but adds a fullness and extra resolution in the chorus and/or final parts of the verses.
The last section of the song introduces a piano over a new chord progression. It adds a new depth to the song emotionally, almost like a sad realization/clarity.
The lyrics throughout has always sounded to me like a person rambling through thoughts in his head until he reaches a point of clarity. The way the instrumental plays in accordance with the lyrics also helps paint this picture.
Hope this helped ?