One place to check out is Woodwick House near Evie on Mainland. They have gigs of all kinds on there and they do have some quite big names. Apart from the Wrigley's cafe in Kirkwall I don't think there are any other regular sessions apart from those already mentioned earlier in Stromness - but don't expect Orcadian music there!