This is a very good question.
Although I have no perfect answer, here are some things you can consider:
Store data in a browser cookie if this is feasible.
Store in the Site collection's rootweb in the Properties, keyed by the user's login ID. You may want to elevate when reading / writing the properties just in case the user has access to a subweb, but not the rootweb.
Take a look at this free tool if third party free tools are on your list. It is called SharePoit List Item Ranking.
If you want to make them reusable across the site collection for each user you can add Fields to the User Information List. You can add a feature receiver to your web parts solution that can create this column or check to see if this column exists in the User information list to be sure that the Column exists.
The User Information list is a Standard SharePoint list that SharePoint uses to store user information. To access the User Information List you can go to the Root web of the Site Collection and use the SiteUserInfoList property
E.G.
SPList userInformationlist = SPContext.Current.Site.RootWeb.SiteUserInfoList;
//Or
SPWeb web = SPContext.Current.Site.RootWeb;
SPList userInformationlist = web.SiteUserInfoList;
To access a users List Item you can use the Users Id to get the ListItem back from the User Information List
E.G.
SPListItem currentUserItem = userInformationlist.GetItemById(web.CurrentUser.ID);
If you are using MOSS you can store this information in the User Profiles and make it available across Site Collections this does not need My Sites to be enabled. You would need to use the User Profile classes to access this.
I would go for the properties on the user profiles. You do not want to store the information on the root web as it is not information regarding the root web. Your example with the favorite urls, each user has a "quick links" collection on their profile. An ideal place for storing urls for each user. :)
Build a webpart that reads/writes a custom database and you'll have the flexibility to use the webpart across SiteCollections, WebApps, or even seperate Farms.
This was implemented where I work and it has been a big success. We needed a way to provide our end users a large selection of important, commonly used links. End users have the ability to display the links that are useful for their particular job function and have a webpart that can be put anywhere to reference those links that are important to them. You also have the ability for an “admin” to go to the custom database and update any URL’s that might change without the end user ever being impacted or ending up with a broken link.