Some people have said they do not sort mail into folders any more but just use the gmail labelling like folders. I use gmail all the time now, primarly to deal with email lists and I use this technique for this and it is a very viable solution.
For personal mail I still like the order of having them in folders; I still use tags (formerly called labels) - only discovering tags mid 06 and they have been a revelation - in this case though. Here are some techniques to improve the inbox madness:
As email comes into your inbox, you can adjust your filters so that next to no mail/once off & don't want to save mail is all that's there. Your new inbox is now your "New" folder and as you add your tags you will automatically have the messages you want to deal with listed.
I made the change in 05 from Outlook Express to
and it's just so much nicer. As described above, you can (colour code) tag any message as Important / Work / Personal / To Do / Later; you can save tagged messages to a folder as described above, this will update as you tag new messages. Just superb.