I ended up buying a NCELL card because they seemed easier available in Thamel. The coverage in the mountain I visited was not as good as Namaste or Nepal Telecom. There is a NCELL center in Thamel where you can get a card for 100rs (it's a little above Pilgrim guesthouse). They are also available through some kind of re-sellers, like photocopytores, but they sell them for 300rs. You need to fill out a form, bring a picture and a passport copy. Also they wanted my fingerprints!
3g worked well with the NCELL card in some parts of the country, but only slow edge in some parts of the mountains. You can buy a data package, but be advised that they add tax on top of the price quoted. Also, they give you a bonus, so that if you buy 500MB you actually get 1GB.
When I went higher up in the mountains, NCELL coverage stopped working. Porters used Namaste or Nepal Telecom in dual sim card phones, and they had no trouble getting coverage high up in the mountains. Not sure about GPRS, but most tea-houses also has working phones, and it didn't cost much to use them to numbers inside Nepal. International calls was rs150 pr. minute.