In the Sati yuga, Nandhi was born in one bull family, from his child hood only he was a great worshipper of Shiva. When Shiva used to perform meditation on Kailasa, Nandhi went to Kailasha to meet Shiva with his father, but from the moment he saw Shiva, he just refused to go back with his father and stayed at kailash only.
Actually Sati told Nandhi to go to Kailasha. But Nandhi did not enter to kailasha, instead just stood at the beginning of Kailasha. Shiva was meditating, he awake and told his Bhoot gana that, there is one true devotee of him who will not enter in kailasha until he welcome him ti kailasha. Shiva went and welcomed Nandhi. This is how they met.
There is also a belief that if you want your message to reach Shiva you can say in Nandhi's ears. While in meditation, Shiva hear only messages from Nandhi only. Many people say there wishes in Nandhi's ears.
According to Linga Purana, Shilag is father of NAndhi who did tapasya to get a son who never dies. Lord Shiva booned him a son Nandhishwara. He was born from Yagnabhumi.(Land of yagna)