So, I've been experimenting with meditating while lying down. This is far more comfortable, but then I have to really fight falling asleep. Sometimes I've succeeded, other times I have fallen asleep. Eating a big meal right before doing any kind of meditation is not recommended if you want to stay awake!
Another tip is to make sure your cell phone is off and you have a "do not disturb" sign on your door. There's nothing more frustrating than finally achieving a deep meditative state and then being interrupted by some triviality.
In the last few days I've tried sitting in full lotus again, and have noticed that it's starting to get less painful -- though one of my legs does has gone totally numb after a while. I've been able to do about one hour of meditation in full lotus so far. The two and three hour meditations have all been while I was lying down.
I don't think I have any definative answers for you on how to work your way up to meditating for this long. I'm just a beginner myself. I think playing chess all my life has helped with my ability to conentrate. On the other hand, in my ordinary life I'm very prone to becoming bored and do a lot of task-switching (especially on the computer, where I spend way too much time), which has hurt my ability to concentrate.
I did find the technique of focusing just on my breath to be very useful. As described in "Mindfulness in Plain English", I try to focus on the feeling of my breath as it enters and leaves the tip of my nose. If other thoughts or feelings come up, I don't fight them, but try to return my attention to the feeling of my breath entering and leaving the tip of my nose.
I've found that this type of concentration is easier on some days than others. On some days I have a lot of thoughts racing through my mind. If I've seen an exciting movie, for instance, I might have a lot of images from that movie flashing through my mind, or I may be thinking of events that happened in that movie while I'm trying to meditate. That's frustrating, and those days tend to be less productive. On other days, however, I might not have a lot on my mind. Those are the days when I can focus on my breath for a long time.