The answer provided by /u/arte_misia provides the technically-correct answer [edit: since deleted]. The only thing I would add is that we are talking about a culture without strict doctrine/dogma. There were no written texts and no strictly-trained priesthood. People's beliefs were likely to have been all over the map, changing from moment to moment, person to person, valley to valley, and continually salted with alternative scenarios and a good deal of skepticism. We cannot apply the concept of religion one acquires in the modern world to a pre-conversion past; today doctrine is defined by books, doctrine, priesthoods, and institutions enforcing and/or reinforcing belief. This was not the case before conversion.

The biggest problem with the way this question is framed is that it attempts to place an explicitly Abrahamic way of viewing things on an orthopraxic religion.

There is no historical evidence that I have ever seen that implies the pre-Christian Scandinavians had any concern about religious belief. There were probably some who were apprehensive about the new god in the south, but by and large, you're talking about an orthopraxic system- that is, a religion concerned with practice, rather than actual belief. Whether someone was a "non-believer" or not was immaterial, religion was practiced because it was simply what you did, because it helped keep the metaphorical wheels greased and kept society going.

As such, there's a better-than-average chance that a pagan Scandinavian would just look at you in confusion if you asked him what he thought happened to non-believers. What we see in the few forms of afterlife known from this period, particularly Valhalla and Folkvangr, entry is based on what you do, not on what you think. These halls were reserved for warriors, not for Odinsmen or Freyasmen. The idea that Odin would turn a valiant warrior away from his hall on the grounds that they believed in a different deity would've been alien to these people.

As hrafnblod says, the emphasis was not so much on belief (this is a Christian, and particularly Protestant idea), but on praxis; what you did was more important than what you believed. This is why early missionaries placed great emphasis on baptism, as the act of baptism saves a person, not what was going on in their minds. This changes somewhat around the 10th century or so, when the pope issues new instructions about conversion of the mind because previous conversion just made people revert to their prechristian habits (eating horse, worshipping idols etc.) when the missionaries left again. Still, the transition to a system of belief was fairly slow.

Note that we definitely can not just use the Edda (or other Icelandic literature) to find easy answers. This is not representative of popular belief, but a highly personal, warped account by Christian elites writing about their direct ancestors.

Burial practices are our most direct evidence of what normal people actually thought what would happen after death. Unfortunately, the burial is a social project intended for the living survivors and family members just as much as for the dead person, so we need to strip off this aspect before we can get to the things that were meant for the dead person. Why this is necessary will become clearer.

Scandinavian graves in the Viking period are very diverse. Cremation is generally the norm, but inhumation also occurs. There is a gradual increase in tendency to bury people rather than burn them over the course of the Viking period, but there are strong regional differences as well. This means it is very difficult to speak of 'the' Viking grave. There are some common traits, though.

Generally, people are buried with a variable number of grave goods. People are buried in their (presumably daily) clothes, which means they carry ordinary household tools (that one would wear on their belt, and hence their costume) or jewelry. Part of this is showing (to the audience for the burial) the person as he/she was in life (of course, idealised by family members). This means that sometimes, young children can be buried with swords because this represents that they belonged to a sword-bearing class (they had right to carry out violence), not that they personally owned that sword. However, it could also signal that people did belief in some sort of after-life, where the dead would 'live on' as they had done in life, and hence needed their stuff. This is more explicit in slightly more elaborate graves, where craftspeople often have the tools of their craft with them. This goes beyond just a symbolic hammer for a smith, for example, and can include larger parts of toolkits, such as coins, weights, and scales for merchants.

When we get to an even more elaborate class of graves, we see that often the buried person is placed in or on a means of transport. This can be a boat (like some of the most famous ones of this period), but can also be a wagon. In the later period, just a horse is given too. This not only signifies the wealth of the owner (and his descendants) who could give up such a mighty thing, but also that it is presumed that the deceased has some sort of travel to make, for which he or she needs a means of transport. This might be an underworld river, like the Greeks had Styx, but perhaps also just a lake or pond, which was not only a common location for sacrifices during this period, but is also the dwelling place of Grendel's mother (and presumably Grendel himself) in Beowulf. The link between water and death thus also exists for Vikings. But not for all, because apparantly some Vikings needed wagons for making the journey.

Now, things get more complicated if you also include the very richest graves. These are usually built as chambers inside a burial mound, and richly furnished with all kinds of stuff an aristocrat needs in his hall (home) to hold a feast (party). It looks as if these grave-chambers are actually miniature representations of the normal dwelling-place of the living. That this was actually perceived as such is found in a number of Norse myths and legends as well, where a would-be grave robber (or a descendant asking for support) is deterred by the 'living dead' in his grave-mound. So it appears that for some, the afterlife is a place that you need to travel to, while for others, it was actually physically inside the burial.

With this in mind, you would get the impression that Vikings did not really have a strict separation between the body and the spirit in the way that a Christian would. What the dead body has is seen to be directly related to what the dead person needs in the afterlife. However, we also have lots of cremations. What to make of the beliefs of those who were burned? It seems that for many, their graves were marked by stones. These could be set in the shape of a ship (or an almond, if you want), a tradition 'borrowed' from the Bronze Age in Sweden and particularly popular on Gotland, but also in other parts of Southern Scandinavia (and particularly monumental at times). More common than a shipsetting (which does remind us of a 'ship of the dead') is a simple triangle or circle of stones, marking a cremation. Whether these also represent something is unclear, but they seem to be primarily intended as (semipermanent) markers, similar to a modern headstone. In the later period, these could be inscribed with runes too, saying something about the dead person (though this is not common and usually associated with the christianisation period). We know that in a grave-field, people would often simply 're-use' the stones of an older grave-marker when building a new one, presumably when the family of the original deceased could no longer object (perhaps because they had forgotten, or too much time had passed and nobody recognised these old graves as 'their' ancestor). This signals that while the intention of the stones is remembrance, the breaking of this memory was also possible. So it is possible that memory also plays a role in how the dead are supposed to be treated.

This is just a short overview of some of the varied burial practices in Scandinavia. You see that things were diverse, even within one region and one period. Possibly, some of these differences can be explained by the personal beliefs of the burial community, or even of the deceased him/herself. However, it is extremely difficult to generalise these beliefs.

If you would like some further reading, I would recommend Raudvere's chapter Popular belief and Price's chapter Dying and the dead, Viking mortuary behaviour, in Price's 2008 book The Viking Age. An interesting well-preserved Viking burial ground is Lindholm Høje in Northern Jutland. You might also want to have a look at the Ladby ship burial as a nice Viking Age example (the more famous Oseberg, Gokstad, or Sutton Hoo ones are technically outside of the Viking Age), or have a look at the article Boat Graves, from Müller-Wille in The Ship as a Symbol (PNM 1). For an idea just how diverse burial rites are, look at Roesdahls Aristocratic burials in Late Viking Age Denmark, in Herrschaft, Tod, Bestattung, 2003.

The Norse faith was not a centralised one, and there might have been several different sets of beliefs.

In one description, there's three afterlives. First, Asgård where those who died bravely in battle end up, where the pig Särimner is slaughtered every night, his pork boiled and magically lasts until no-one can eat anything more and mead flow endlessly from the teats of the goat Heidrun for the brave warriors to drink.

I can't remember ever reading that there were any kind of requirement to believe in the Norse Gods to have this afterlife - however, it is quite possible that the Norse believed that other religions could be true as well - gods were tribal or geographical in origin, and the Norse gods ruled in Scandinavia while other gods might rule in other places. In Frans G Bengtssons epic Röde Orm (The Long Ships or Red Orm in English translations) the Norse pays respect to Islamic ruler they serve in Spain by converting, since this god is strong and has many followers in that land (the book is fictional, but generally considered very well researched).

The Norse mythology includes two other places where people could go - Hel and Helgafjell. Hel was the realm of the godess Hel, who was wounded in being thrown down to her realm. She is pale but beautiful on one side and deformed and blue-black on the other. Those that have lived a moral and good life end up on Hel's pale side and have a decent afterlife, while those that have been wicked, immoral or evil end up on her deformed side, suffering hunger, lack of sleep, starvation, illness and disease, unhappiness and devastation.

Another afterlife in the Norse faith is Helgafjell which is described as a place for those that did not die bravely in battle but lived a moral life and did their best. Placed under a huge mountain, where large fires kept everyone warm and families and relatives could re-unite and talk of what had happened and old memories over good food.

Another afterlife was that of Folkvang where warriors who did not die in battle could end up - in some versions, half of warriors that end up in Asgård are in Valhall and half in Folkvang.

Generally, the Norse usually believed that you ended up in the afterlife of your own religion and your own gods, especially if that relgion was the dominant one where you died, since gods were strong among their tribe or geographical location.