Finding out that an ancestor was born at sea can lead to a dead end. But it is possible to find out birth records of those born at sea, especially if you know what nation the ship was registered to.
FreeCEN can help identify which vessel a sea-going ancestor worked on if they were at sea during the previous census, and that can help identify which archive might preserve records relating to it (and others in the company). The National Maritime Museum has more help with finding sea-going family.
The National Archives (UK) states that any record made of a birth or death at sea from 1837 onward was sent directly to the General Register Office and recorded in the Marine Register. See their guide, here.
Unfortunately, digital records of births, marriages and deaths at sea on board British ships incur a cost to search them. Find My Past allows you to search the indexes of the General Register Office and National Archive overseas records of births, marriages/banns and deaths/burials. They also allow you to search for an individual ship should you know its name. Be warned that some years are absent from the record, and any marriage which took place on board a merchant ship was not legally valid.
Most records from ships that belonged to former colonies were retained within the former colony and are most likely not held at the National Archives, but 'elsewhere' can still be in the UK. For instance, you can use the British Library's department search for Asia and Africa to look through records that include those of births, marriages and deaths at sea.
Passenger lists can be of great help: FamilySearch has over 200 record sets in their Migration and Naturalization collection, most of which are passenger lists from various countries worldwide. Olive Tree Genealogy have searchable passenger lists for the USA, Canada, Australia, New Zealand, South Africa and England.