Help!

I am having some trouble finding information on my great grandfather, Olaf Martinsen. He was born February 5, 1857 in Frederickstad, Norway. His parents were Martin Jorgensen & Inga Oline Jensen. He emigrated to the US around 1880. I cannot find them on the 1865 census. Does anyone have any suggestions? Are the sites http://www.rhd.uit.no/folketellinger_engelsk_britisk.html & http://digitalarkivet.uib.no/ pretty much the only sites that have the censuses? Are they complete?