Also note that that job offer is highly subject to going "poof" when there's that long a delay to your first day of work. Certainly don't give notice before you're seriously committed (e.g. bought a new house "over there").
I've seen too many situations where someone has relocated only to find out the company really doesn't have a job for them anymore.
Worst was when MIT executed the Applied Biology department in the middle of the night, with one new junior faculty member who'd turned down other good offers showing up right then, family and all as I recall. I also had a roommate who was going to start as a grad student that fall....
I cite the above because the people hiring you might not have the power to keep their word. Depending on the market, internal politics, etc., they might not even have jobs 3 months from now. The Applied Biology faculty and staff made those offers in total good faith, they just lost their ability to make good on them (because they were too good at getting research money, but that's another story).
I like to think it depends on your character and that of your current boss or company.
If it is a situation where you think that the boss will be happy for you, and will want to get the most benefit of a smooth transition while you're still around, and you feel it is the right thing to do, then I'd let them know as early as possible. It's always good to keep things in the open if you feel comfortable doing that. Who knows what will happen.
If, you don't have a great relationship with your current employer or boss, and suspect that they won't keep you around or treat you properly, then I'd say the two week minimum is probably called for. If they aren't respectable people, maybe they'll fire you, but you can rest assured that you've done the right thing, and you just got an extra two weeks for your move.
If you have an excellent relationship then it won't matter since they will be happy for you and are aware you'll be leaving.
Do make sure you have the other job prior to giving notice.