So, I just made my first all-grain brew a few days ago. Needless to say, I wasn't really sure how to do it, so here is what I did. Maybe it will help you out. I learned most of the information here from the guy at the Modern Homebrew Emporium in Cambridge, and Homebrewing Guide by Dave Miller. I am describing the step-mashing process, which is one of a few different popular methods. If you've tried one of the other methods, I'd love to hear about it.
This process will add a few hours on to your brew time, and really make it into an all-day activity, but it will give you much more control and satisfaction over the end product. And, anyway, you don't brew your own beer because it's easy, right?
I am assuming that you know how to do a basic extract-based brew, so I will just focus on the mashing process. After that point, it is the same process, except that you will have to boil more liquid. If you have a pot big enough to hold your whole batch, then you are all set. However, you may have to split your batch into two pots, like I did.