The Colonial Fleet is either the primary or a large armed service branch of the Colonial Defense Force, under the jurisdiction of the Ministry of Defense.
The Colonial Fleet operates in tandem with another branch of the armed services, the Colonial Marine Corps. The Colonial Fleet also has a Reserve branch, of which Lee Adama was a member (Final Cut).
The Fleet was presumably based at Picon Fleet Headquarters, and was under the leadership of Admiral Nagala at the time of the Cylon Holocaust. Other identified Fleet installations included the Scorpion Fleet Shipyards, Ragnar Anchorage, and the Armistice Station.
Known Ships
By the time of the Cylon holocaust, the Colonial Fleet included approximately 120 battlestars. The existence of Battlestar Groups strongly suggests that there were other military vessels in support roles, akin to an aircraft carrier battle group.
As noted in the official Sci Fi Channel Battlestar Galactica web site, the Colonial Fleet also included modified Space Park vessels (although the single Space Park liner shown in Galactica's rag-tag Fleet is very likely a civilian liner).
Battlestars mentioned destroyed in the Cylon Attack included Triton, Solaria, Columbia, and Atlantia, commanded by Admiral Nagala. According to Admiral Helena Cain, two unnamed battlestars and three other ships (type unknown, but presumed military vessels) were destroyed in the Fall of the Scorpion Fleet Shipyards.
Currently, the only two Colonial Fleet capital warships known to have survived the attack are the battlestars Galactica and Pegasus, which guard a fleet of civilian ships.
Notes
In the Mini-Series, William Adama tells Kara Thrace when she's released from the brig "We lost 30 battlestars in the opening attack". She responds, "That's a quarter of the fleet". This establishes that there were approximately 120 active battlestars at the beginning of the Mini-Series.