Depending on what MOS he's going in there could be quite a bit of additional training. First he will be sent to either Camp Pendleton in CA or Camp Johnson in NC for additional training (its been so long since I've been with the Marines I can't remember what its called, but I'm sure someone will know). After that he'll go for the specialized MOS training. I couldn't say how long it would be before he would have to head out, most likely depends on the unit he gets assigned to.
As for a good graduation gift, cash was my best friend, but if you are looking for something tangible, and especially knowing he's going to be going overseas soon, I would look into an ipod, or MP3 player. They are small, and and can help one to "get away" from it all. A little privacy, even if its just blocking out all the sounds around you, is worth its weight in gold.