Few times a day there're songthaews to Viengxay which will leave from Southern bus stations 4 km from town. In 2009 we paid 10 000 KIP per person for a ride which took us about one hour to get there (SN - Viengxay).
Songthaew to Vietnamese border (leaving SN at about 6 am) will pass Viengxay at the outskirts of village so you'll need to walk some kilometers to the town. From Viengxay you can catch that bus by the main road and wait there untill it pass - we were told to be there at 7 am and we had to wait half hour more before it actually arrived. Viengxay to Nam Soy takes 2 hrs through scenic mountains and agricultural landcape. For that distance you'll be charged 20 000 KIP (altogether SN to Nam Soy takes 3 hrs for 30 000 KIP if you go this route directly). Wear something warm beacuse it can be quite windy and rainy here. Road is paved and looks better than on the Vietnamese side.
There are few tuk tuks in front of the provincional bus station which can take you to town if you don't like or want to walk. They charged 5000 KIP per person for a ride to the guesthouse.
From centre of town to the southern bus station (for Vietnam, Viengxay direction) we were charged 10 000 KIP. That bus station is 4 km from diamond sculpture and since they're not many tuk tuks yet in Sam Neua you will need to stand some time by the road before one will pass. Go find them by market for faster transfer.
At the time of this writing it is possible to fly from Vientiane to Sam Neua with Lao Airlines and it can save you a lot of time. The plane I went on was really neat. Only 17 seats and they leave the door to the cockpit open. Landing is spectacular on this little airstrip in the mountains. Just don't do it if you have a phobia about flying.
For the moment the bus station is right in the center of town near the market. You can get from here to Vieng Xay to see the caves (10,000 Kip) - takes about an hour and a half through some really beautiful scenery. Buses also run to Nam Nouan, Phonsavan, and there is a really long one to Vientiane. You also get the bus here to go to the Viet Nam border. Nothing is posted in English but everyone is really helpful and I managed just fine with pointing and sign language.
Apparently the station will be moving out of town in the near future.