How about a specific area in the forums where fleets can post recruitment threads and other things pertaining to their fleets?

There would only be allowed 1 topic per fleet. So if a fleet makes more then 1 topic about their fleet, all their topics would be removed. This way you don't have 1 fleet flooding the forums with fleet spam.....

Also you could have a stickie in the forums which shows each fleet, their officers, who to contact, their logo and other information. This way the players could keep track of the fleets.