In addition to Dan Larson, I can also highly recommend Olaf (Chris) Hendriksen of Boston Catlines (617) 776-8688 for appropriate mandolino strings. You will have to give Chris the string-length of your instrument and your favored reference pitch (A-415, A-440, etc.). Chris really knows his stuff and in my experience his sets can really bring out the best in an instrument. Chris will often make sets up from his own gut (I think), as well as Savarez, and Pyramid strings.
As for gut vs. nylon, I have to come down strongly on the side of gut for both sound and feel. My gut-strung mandolinos are indeed very stable and I wouldn't necessarily reject gut based on its reputaion. It also seems that gut has a certain "stiffness" that works better than nylon at moving the bridge (and creating a bigger sound). Nylon was somewhat less well known in the 18th century... :-)
Of course, gut strings aren't cheap... but in my view there is no real substitute if you're after the original sound of an early instrument (excepting the odd wire-wrapped silk string, as Eugene mentions).
"The effect is pretty at first... It is disquieting to find that there are nineteen people in England who can play the mandolin; and I sincerely hope the number may not increase."
- George Bernard Shaw, Times of London, December 12, 1893