Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
The best way that I have found to do it is to do it in iTunes.

1. Go to iTunes and to the play list that you want to arrange the songs in.

2. Decide on the order that you want the songs to appear in, then click and drag the song to the position you want.

3. As you drag the song you will see a thin line appear following your movement up and down the list. This line represents where the song is going to be positioned when you release the click and drag.

4. When the song is in the position you want it release it.

5. When you have all the songs in the order you want sync your iPhone and the songs will appear in the new order.

I hope this helps you.
 
The songs do not appear on the iPhone in the same order they are in on iTunes.

Are you using iTunes 9 and/or iPhone OS 3.1? This appears to be a bug with one or other (or both) of these software. I'm afraid we just have to wait for Apple to fix this. :(
 
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.