13
Update: ASP.NET Web API is now the best way of creating a REST service for .NET, there are plenty of tutorials online: http://www.asp.net/web-api
Pre-ASP.NET Web API answer: I also found there to be a lack of documentation on this. I mostly followed this tutorial, which can be easily understood and thus implemented in VB.Net.
There are also quite a few decent templates of WCF REST (VB.Net) that can be downloaded via Online Templates in Visual Studio. You might want to look at WCF REST Service Template 40(VB).
There's also the WCF REST Starter Kit Preview 2 on Codeplex.