Kinda a big question. There are different ways of thinking about it. Some people think first and foremost about melody, although I suspect most of them are really thinking about melody in the context of some harmonization they're "hearing" subconsciously, and obviously melody implies at least some hints at rhythm. At it's simplest, this approach just involves "humming a tune". Any notes in any order or any length for each one work as a melody if they sound good to you. With that said, most of the time, melodies will have some kinds of patterns in them. Think about twinkle twinkle little star. Think about the first phrase short short, short short, short short, long with the short short pairs rising in pitch. In the second line, this same rhythmic pattern repeats, but with the short short pairs descending. This is the kind of pattern that is typical of melodic music. The patterns can be simple or very complex, but they're usually there, and they're one of the main things that distinguishes a pleasing melody from a random string of notes.
In this "melody first" approach, the next step is to create harmonic support for the melody. There are a thousand different ways of doing this, so I won't try to describe it in detail other than to say it amounts to finding a pattern of other notes that when played or sing together with the melody will create pleasuring and interesting sound.
This can be in the form of a counterpoint melody (or two or three) that will typically share the rhythmic patterns of the melody, but at different pitches that form harmonically pleasing interactions of sound. The counterpoint melodies will sometime go up in pitch at the same time the melody does and sometimes go in the opposite direction, but the musical distance (interval) between the melody and the counterpoint will be carefully creates so as to achieve the harmonic intent of the composer. This is typical of the way Bach composed. And is also typical of four part harmony "church music".
Harmonization can also come in the form of selecting a series of chords that work with the melody, chords being 3 or more pitches played in the same time space.
This approach is much more common in modern music, really from the romantic period through modern pop. Beethoven's Moonlight Sonata is an absolute masterpiece of chordal harmony supporting a melody. Any modern pop song works the same way, with way less complexity.
Speaking of moonlight sonata, of course I don't know exactly how Ludwig Van came up with, but I'd bet he DIDN'T use the melody first approach. I suspect he went the other way around (my preferred approach) and developed the harmonic movements first, and let the harmonic progression inspire the melody.
In the approach, you' d start with a series of chords, in an order chosen to convey the feel, or emotion, or spirit of what you want the piece to communicate, and then compose a melody that works within that harmonic space.
I don't know what instrument you play, but if it's guitar or piano or any other instrument that can play more than one note at time, just start playing through a series of chords that fit together in some way (a thousand ways to think about chords fitting together). Let's say it's G Em C D7. Just play them over and over and develop a bit of rhythm that you like. Now start humming melodic phrases that work. Paul Simon has said he writes songs this way by singing gibberish lyrics to a chord progression he likes until he's devolved a set of melodic idea that inspire his lyrics.
Most modern songs will use one set of chord changes for verse content with some kind of build up into a (typically) more emotional or energetic chorus part that has a different set of chords. And melody. Usually, in this format, there's a bridge part somewhere in the middle that's made up of a third set of chord changes, which is usually similar to but slightly different from either the verse part or the chorus part, but with a different melodic and/or rhythmic approach. Sounds like a formula, but within that structure there's enormous flexibility.
Loooong answer to a short question. I hope you find something I've written her of use.
-J