The Basics
Whenever you've written a melody, there are a set of chords or harmonies that we may 'automatically' hear. For example if it's a simple melody that doesn't move around much or have any weird leaps and accidentals, we will probably hear a basic I IV V I. Since we hear these progressions so often, we may automatically hear them in our head. That doesn't mean that we have to use them, or even that they're 'right'. For example if you have a simple melody you may want to use other chords because you want a different 'feel' for the song. Or, you want to invoke some surprise, or you want to change it into a different genre, or you just may want to make the song 'more interesting'.
Substitutes
I had an interesting thing happen when teaching recently. A student came in with a well known song and a sheet of the chord changes. The chord changes in fact turned out to be wrong but they also fit. When correcting the changes, the song was infinitely better but both sets of chords could have been used. The 'wrong' chords were your basic I IV V whereas the correct ones used substitutes instead. Substitutes are chords that are familiar to the chord they're replacing but not exactly the same. These chords function in the same way as the original chord. A substitution that is used a lot is the vi chord replacing the I. For example an Am would go where you would expect a C chord to go. If you want to hear how this sounds, write a simple melody over a F G C progression. Play the progression a couple of times but the last time, put the Am in place of the C. Make sure you don't change the melody, See how this chord fits but 'changes' the melody even though we're using the same notes. The iii chord is also another substitution for a I chord.
The
One thing substitutions do is create an element of surprise because you're expecting one thing but get another. The way to do this is to replace the expected chord with non-diatonic chord. If you were writing the song in the example given above, and were looking for a substitute for a C chord, you could replace the chord with another that has the melody note in it. For example if the melody note was an E, you could replace the C chord with an A, E, or C#m. You could even go up to the 7th and try an FMaj7 or F#7. All of these chords have an E in them. If the note was a G, you would have different options. You could replace the C major with a Cm because that critical 3rd, isn't in the melody. But, you could also use Eb, Gm, A7, or AbMaj7. Remember these are ideas just using the melody note as an anchor. The possibilities and endless...
Simplfy
Since we're talking about substitutions, we have to talk about changing the harmonic background completely. Moby did well with his Play album by taking old blues songs and placing them on electronic beats and different chord progressions. Just becuase the original had a chord change every bar, doesn't mean you need to. Dance music does this all the time. Instead of having the regular changes, remixers will simply place the melody over their 'static' harmony*. Jazz and blues musicians also do this regularly. They will take the basic form of a blues and embellish the chords and changes. Sometimes this is done to extremes as in the case of John Coltrane who created his own version of 'blues changes'. Their are many more artists that have done this. Sometimes, in the case of many pop songs, entire changes can be replaced with a single chord or vamp.
*I use the word static here because most dance music relies on a constant underlying groove and harmony. It doesn't have to be this way but remixers will usually replace any harmony with their own.
Elaborate
Of course if the harmony can be simplified, it can also be made much more elaborate. This is pretty much the standard for jazz standards. Jazz musicians will usually take the given chord changes and replace them with their own. The best musicians pride themselves on having the coolest changes. They often do this without changing the melody*. This isn't just a jazz thing though. Musicians love taking songs and changing the chords and voicings. A folk musician might add some 2nds and 4ths. A pop musician might add the same as well as some dominant and minor 7th chords. Instrumentalists might go even further to add some interest to their instrumental versions.
*Jazz musicians will often change the rhythm and paraphrase the melody but will usually try to keep it close to the original. Of course a Dixieland band will play the melody completely different than a Bebop combo.Written In Stone
As you can see, the chords you choose for your compositions is a personal one. There is never just one solution to which changes will go to any given melody. It really is up to the writer. Once you get to know this, you will spend more time thinking about this different changes that you have in your composition toolbox and hopefully make your music infinitely more exciting.