Here's a thread with a sort of relevance:
http://www.themodernantiquarian.com/forum/?thread=28944&offset=125
The campsite at Stornoway is quite decent, has good bunkhouse things if it gets too wet/cold/windy for the kids.

when we went we got off the boat and followed a sighn to a camp site, the old dear told us there haddnt been a campsigt there for years (i did onder the shower was in a caravan and the tarrif on the window was in shillings haha) i asked her if she knew of anywhere else, she told me to wait while she went inside, i waited for ages then she tottered back out and said "oh noooo dear a caaant think of inywheer" she said that folks on harris didnt mind if you camped anywhere, so thats exactly what we did. There was a place that i recal was about 2 quid right next to a gorgeos beach on harris though, nothing but a tap as facilities go, but if you take a shovel it'll be right grand.

http://www.undiscoveredscotland.co.uk/areawestnorth/self.html

The above should give you most information that you need, however as has already been said most people on the islands are generally OK about camping on their land as long as you look after the place.

But please remember that the machair ( http://en.wikipedia.org/wiki/Machair ) is all ecologically precious and you should never camp on it and also take care not to disturb when out walking etc'

Wrap up warm ... even in the summer it can be a wee bit chilly!

;-)

As a matter of interest, when're you going? There's a lot of us gonna be there in July http://www.themodernantiquarian.com/forum/?thread=28944

love

Moth