They are listed in your Market's Downloads page, whether or not they are installed. If they're not installed, they're notated with the text "PURCHASED" where it usually has a price or "Installed"
After I did a factory reset, all my paid apps were still flagged as purchased in the market. I believe the purchase is tied to the main google account you used to set up the phone.