We went to the Orkneys for 5 days back in September last year by camper van. The advantage of this is that you can get to and stay near nearly all the sites you'll want to see without spending on B&Bs, hotels or unnecessary journeys (you can free camp just about anywhere in Scotland as long as you're not annoying anyone or trespassing). Camper vans can be hired for as few as 3 or 4 days if you can get your booking in early and I think if the van's not too big you can travel on most of the inter-island ferries, again pre-booking these.

A nice place to stop the night is the Brough of Birsay, right up in the NW of Mainland. It's not prehistoric (Pictish/Viking), but interesting and you can walk across to the tidal island at low tide to view the site. There's also a public toilet and shop in the nearby village.

Have a good'n!