Adding an extra join or query on the most heavily used script isn't really a good idea... At least not for a function that doesn't give much extra information.
Maybe every time someone logs in all users online status would be updated? That script isn't run very often, but it should keep it fairly up to date. Also, the online page could do the same thing, so that it is possible to catch users who have left since the last login.
