I was told that the Northern Territories have never become a state, so do not have seats in parliament, yet those who live there are "obliged" to vote. What do they do with the votes?

Jo,

It's true that the Northern Territory (note the singular) is not a state; it is one of two territories that together with the six states forms the Commonwealth of Australia. (The other territory is the ACT, Australian Capital Territory, an area of New South Wales that was excised to allow our "artificial" capital Canberra to sit on "neutral" ground).

However, the NT has its own Legislative Assembly (similar to a state government but with more control still vested with the Federal government). Voting in elections for the Assembly is compulsory for Territorians. Also, as Australian citizens they are obliged to vote at Federal elections, for their one (soon to be two) federal representative in the lower house and two senators.

Interestingly, a recent referendum in the NT rejected becoming a state.

Further reading:
http://www.nt.gov.au/ntg/information/administation_history.shtml