I've been on Jekyll for a while now for my personal blog, migrated from Blogger. Hosting-wise I'm on S3, which is very simple to setup and very cost effective. I would agree that the easiest way to get started is to essentially copy someone else's setup on Github and then modify what you need.

Blog: http://www.ohscope.com and my S3 push setup: http://www.ohscope.com/2011/02/20/s3-jekyll-deployment/