We’re sponsoring a developer to work on this as a plugin. Approach #2 seems like the way to go for an MVP. I’ll post a final spec below based on @mcwumbly and @LeoMcA’s mockups.
Some modifications:
- The primary place of interaction should be the /categories page, where a star can be clicked to favorite a category. (mockup below).
- I don’t think it should be added to the Notifications page. Favorites will have no effect whatsoever on notifications. I’m opting for the Interface page instead.
SPEC: Favorite Categories
1. Expose a star button on the /categories page
Stars in /categories are /hidden with toggle same as we do with topics: 
Categories
(Could also see how it looks with stars left-aligned on parent categories as well)
Sub-categories
2. Add a Favorites list to User Preferences : Interface page.
3. Show “Favorites” in category drop-down
If any categories are added to Favorites, a Favorites tab is visible on the topic list page.
If the list is blank, “My Favorites” won’t show.
Assuming the user is doing something like watching feature, tracking #howto:admins and favouriting plugin and ux, user would see the following (shown here as “my categories”):
my/latest
my/new
my/unread
my/categories
(Clickable Stars missing in mockup. Also, this screen might not doable.)
Stretch goals:
- Favourited categories should be listed at the top of /categories and in the categories drop-down.
- User can set “My Categories” as their default index
- Admins can define a “My Categories” preset, so registered users are already set up with some default Favorites.