If you're starting from a brand-new MacBook, I'd suggest removing the hard drive and swapping in the new one straight away, then putting your restore DVD in place and booting up (pressing "C") and run setup on the new drive that way.

The only snag you may run into is that your new drive won't be formatted out of the box, but setup should (note I said "should") initialize it for you.

You won't hurt anything by removing the factory drive at the start. Just make sure you have power to the MacBook while you're loading the OS-- you'll charge while it's plugged in.