The above writeup has some very good information. As Stealth Munchkin states, the best way to start songwriting is to learn other people's music first, and to learn the basics of music theory. This gives you the instinct you need to get the really catchy melodies. Nevertheless, I thought it would be good to give a bit more practical advice. Using the following methods will give you some pretty mediocre music if you're just a beginner, but the point is to improve, which is something you will do, if you keep at it. Note that this advice works best for the guitar, although it can be adapted to other instruments.

When writing a song, you can start from one of two places: The chords or the melody. As a beginner, you'll find that starting from chords is a hell of a lot easier, but it also tends to make for sometimes uninspired music. The melody method makes for better music, but is also harder to pull off.

Starting from chords:

The first step is to understand which chords fit together in a given key. Others have already written extensively on this subject, so it is not something I will focus on. Click here for more information. I will assume you know what all the chords are from here on out.

For now, I'll just start with the key of G-major.

In this key, you have the following chords:

G Amin Bmin C D Emin F#dim

Or if you want to start with some more complex chords, you have:

Gmaj7 Amin7 Bmin7 Cmaj7 D7 Emin7 F#dim7

Now that you have these chords, mess around with them. Find some chord progression that seems nice to you. Don't go crazy, just get a couple measures that flow well, and are easily repeatable. Don't worry about rhythm yet, just play a chord once per beat (probably simple strumming on the guitar, but again, feel free to try on other instruments), or something equally simple.

Once you've got that down, start humming while you play this progression. You'll notice that you instinctively start humming notes from within the chords, and as you change chords, the notes you hum will probably change as well. That's it, you have your basic melody.

From here on out, it's just tweaking what you've got. Start messing around with odder rhythms, add some extra notes where you think they fit. Repeat these steps in the same key to get the standard verse and chorus combination.

Starting from a melody:

The first thing to do in this case is to start playing notes in a key, until you find a melody that you like. The alternative is to take a tune that you've already got (i.e. one that just came to you while you were walking), and transcribe it. Find out which notes you've been humming, and which key they're in.

Then write out the notes you've played, and below that, all the chords in that key along with all the notes that belong in a given chord. For example:

Again, say you're in the key of G, and have a melody that plays the following notes (Yes it's very simplistic. Write your own damned music.):

G A B C B A B G

Below that, each chord in the key of G:

   G        Amin       Bmin        C        D         Emin      F#dim
 G-B-D      A-C-E     B-D-F#     C-E-G    D-F#-A      E-G-B     F#-A-C

 Gmaj7      Amin7      Bmin7      Cmaj7     D7        Emin7     F#dim7
G-B-D-F#   A-C-E-G    B-D-F#-A   C-E-G-B  D-F#-A-C   E-G-B-A    F#-A-C-E

So we see that a G-chord has the notes G, B, and D, etc. Now just take the notes in your melody, and find out which chords they fit in. Ignore any notes that you sing quickly. These are passing tones that won't affect the overall harmony much. So in the example above, G and B fit in a G chord. And the A would simply make it a Gadd9 chord. (You did check out that link, right?) So try playing a G chord while singing those notes, and see how it sounds. Don't like it? Emin has the same notes G and B, try that one, see if its any better. Or Amin7 has the notes G and A, while Bmin7 has B and A. Try them all out until you find the chord that "fits". You'll know it when you hear it. Do the same for the rest of the notes, until you have your chord progression.

After that, it's just tweaking again. Find a rhythm that complements your melody. Spice things up a bit.

With time, these methods will become more and more like second nature. You'll find the note you're singing, and just intuitively try it with a few chords until you find the one you like, and often will guess the next chord before you even try it. Keep practicing. Like all of music (maybe all of everything?) the key to getting better at songwriting is to just keep plugging away, be it by playing other people's music or working to create your own.