I have a feeling that it's tied to stuff in online mode. Is this the only way to unlock skulls?
Skulls are generally unlocked by finding them in the single player levels, but they're hidden very well, and in some cases require you to take specific actions in order to be able to get to them. In some cases it means jumping on top of a vehicle to get to a hidden location, and other times it means going the wrong way and exploring areas the game seems to try to keep you out of.
This site has a full list of all the skull locations in Halo Anniversary. Most of them are pretty sneaky, so don't feel bad about using a guide. :)