How to power up BeagleBoard-xM using batteries?
I am fairly new to this stuff as well but I will do my best to answer your question.

I do not believe that four 1.2v batteries will be sufficient on their own (at least not for too long) because of the inevitable voltage drop that will occur over time.

Most NiMH batteries I have come across have between 1800 and 2500mAh and four of these will be able to run your board for a while before they lose the ability to source 750+mA, but when they do it will cause the supply voltage to drop below 4.8v.

I see that the typical max current supplied by the USB ports on the board is 1500mA, and assuming outbound USB current was not factored into the typical average current draw of the board, it could mean that as much 2250mA could be needed at any given time. (maybe even a bit more, I don't know enough about the beagleboards to say). At that level of current draw it wouldn't take very much time for a voltage drop to occur. 

I would instead use a switching regulator to power your board. I looked briefly but didn't find many prefabricated "boost" converters that would supply sufficient amperage, but I did find a lot of "buck" type converters that would take a higher input voltage (say 7.2v, from six batteries) and convert it to 5v 2A+ at the output.

You can also do a little research and build your own buck or boost converter instead of buying one, or take a simpler approach and build a linear regulator, but these are not as efficient and you wont get as much run time out of your batteries. 

The max current draw may(MAYBE, not sure) also be something that is only approached infrequently in quick spikes. If this is the case then it may not be necessary for your regulator to source the max current, but it would mean that you should put some extra capacitors in your regulator's output stage to handle instances of increased current draw.

I hope this helps. :)