Sossusvlei is the tourist point for 'exploring' the desert which, for the hitchhiker wanting to really go to an amazingly beautiful unique place in the middle of nowhere, is rather good seeing as its relatively easy to hitch a ride with people going there in their rental cars or something.
Some people go south from Windhoek and turn of the B1 a few kilometers south of Rehoboth, some people take the C26. Both should be rather doable but the former option worked fine, the latter is unconfirmed.
This is a touristy spot, so there are people trying to not let people free camp. Essentially a lot of people want to see the sunrise in the desert so you can't get past the checkpoint which makes sure people pay for accommodation if you don't stay on one of the luxury lodges (and have a paper from them) or inside the campsite (which costs a lot of money). If you follow the instructions for how to dodge the fee you'll be able to outsmart the people trying to charge money to see a sunrise.
There are ways of avoiding paying the rip-off camping fee if you don't have a vehicle, simply waiting with setting up your tent until well after dark and then get up way before sunrise is recommended. A lot of people leave from the campsite 1 hour or so before sunrise to make it into the desert to see the sunrise. Talking to people around the campfires in the evening might help arrange a ride.