From Muppet Wiki

Nelson is an officer of the Royal Canadian Mounted Police. In a Season 14 sketch on Sesame Street, he sang "Indian U Call" with Jeanette.

His name and uniform are a spoof of singer Nelson Eddy's role in the 1936 film Rose Marie.