Really it's not that hard. But, if you're picky like me, you not only want your blog posts to have the URL prefix, but also your category, tag, archive and author pages as well; pretty much anything related to the blog portion of your website. This proved to be a little more difficult to figure out, though I eventually did thanks to help from people over at WordPress StackExchange.
As a quick note/warning, this will not work if you have a sub-directory on your server named “blog” or if you have a sub-domain (which would make a sub-directory) on your server at blog.yourdomain.com. Also, if you're like me and used to have a blog at a sub-domain like that, you will have problems setting up redirects. I'm currently looking into a solution for that now, but no one seems to know how to do it. Once I figure it out I will post it.
At any rate, here's how to setup the URL structure.
First, you will need to setup WordPress to use a static page for your homepage, and a different page for the index of your blog (the page that shows all your recent posts). If you're using WordPress as a CMS, you've probably already done thing, but in case you haven't, here's how to do it.
Create two new pages. One will be your static home page, and the other will be the index for your blog. The page you make for your homepage can contain any content you want, but the page you create for your new blog index should be left blank. Also, in order to keep the consistent URL structure that we're trying to create, be sure the URL slug for your new blog page is just “blog.”
Once you have your pages created, under the Settings header on the left hand menu, click on Reading. On this page, you will see the Front page displays option. Select the A static page option, and pick the two correct pages from the drop down menus. If done correctly, your blog index should now reside at a URL like www.example.com/blog.
Next, you will need to edit your .htaccess file to remove the /category/ prefix from all of your category pages. By default, WordPress will make your category URLs look like this: http://www.example.com/category/category-name. We want them to look like this (for now): http://www.example.com/category-name.
To accomplish this, add the following line into your .htaccess file. Be sure to keep a backup of your .htaccess file, don't overwrite anything that's already in there, and be sure to change the website URL to your own.
RewriteRule ^category/(.+)$ http://www.your-website.com/$1 [R=301,L]
After that, go back to your WordPress admin panel again. On the left hand menu, under the Settings heading, click on Permalinks. This will bring you to the page where you can edit your permalink structure. You will want to setup your permalinks as follows.
Select a Custom Structure for your common settings, and set it up as /blog/%postname%. This will make your blog post URLs look something like this: www.example.com/blog/article-title. If you had something for a Custom Structure already, just add /blog/ before it.
For Category base, put in /blog/category. This will make your category links look like this: example.com/blog/ category/category-name. The reason we had to first remove the category prefix using the .htaccess file is to prevent WordPress from adding the prefix where we didn't want it. Without first removing it, our URLs would have looked like this: example.com/category/blog/ category/category-name. While I don't think it's supposed to happen that way, I did run into that problem, so first removing it to give us a clean slate was the easiest method I found.
With regards to the category setup, I received the following comment from Ian which may be useful for some:
If you leave category base blank and add "/blog/" to the custom permalink you won't have any need to customize the .htaccess file. In fact, you probably shouldn't because there are several plugins that end up overwriting .htaccess for their own purposes...if you have any of those, you'll have to add it back in every time you make a change...
Finally, for the Tag base, add /blog/tag. As you can probably guess by now, this will give you a URL that looks like this: www.example.com/blog/tag/tag-name.
You should now have a nice, organized URL setup for your WordPress-based website. If you run into any problems, don't hesitate to leave a comment.