Andersen = son of Anders
Andersdatter = daughter of Anders

Norwegian family surnames were established by law in 1923. Before that most Norwegians used real patronymics, individual surnames. Some upper-class and town people had started using family surnames from about 1850.

In 1865 census there are about 27 000 men with given name = Anders. Their sons then would get Andersen as surname (individual). Later on these sons might start using Andersen as a family surname. So most Andersens are not related to each other.
Check the children of some 1865 census Anders given names: http://digitalarkivet.arkivverket.no/ft/sok/1865?fornavn=and...=