It happened to me too. You need turn on your Wifi or 3G, depending on what type of Kindle you bought, then go in the Menu-->Settings-->Registration-->Register.
You'll be asked for your amazon account email and password... and you'll be registered!
If you don't have an account with amazon, you'll need to make one
Welcome to MR!