Ah yes, Apps in Windows 8 :-(
OK, I just went through it with my Windows 8 system. Sure enough the 20 year old tried and true way of doing this has been changed for reasons that only MS knows! Here's what you need to do.
1) Wiggle the mouse in the upper right corner of the screen to get the charms.
2) Click Search.
3) Type in Solitaire in the search box.
4) You'll see solitaire's icon to the left, right-click the icon.
5) Now look down at the bottom and you'll see an uninstall icon - click on that.
As far as I'm concerned this is just more evidence MS has lost touch with its customers.