This is because we all use an app from the market called "titanium backup" which saves the data of every app, the app itself, data from the phone system, and the link to the market. All kf these options are customisable and interchangeable. You'll want to purchase the licensed version because that will automatically restore apps with the touch of a button, as where the free version requires you to manually approve every app you restore. With the rate you will be using this vital tool, it is really pennies-on-the-dollar.
Naturally, to restore these apps you musn't let your Google account restore your apps upon first startup. Don't worry about the market not recognizing them, after your first initial reboot after restoration, everything will be as it once was. Really a smooth process just time consuming to wait while things restore. I usually flash at night when I have a good 2 hours to dedicate to my phone explicitly.