In the last version of POP Forums, I stored the users online in an Application variable. Surprisingly enough, the performance wasn't bad, even though I suspected it might be once you had a thousand users or so. I opted to do it that way instead of hitting the database to see when the last “hit” by a user was, because I wasn't that into updating that field on every page request. I know the www.asp.net forums does it that way, and periodically caches.
It's a six/half-dozen kind of trade-off. What would you do? I'm working on the Whidbey version now, so this is as good as any a time to change it. I'm somewhat influenced by the MembershipProvider, because it's probably best that I get on board with the scheme that's built into the framework.