So I figured this out after a lot of digging. As it turns out, I had to go into my theme's functions.php and add this line:
add_theme_support( 'post-formats', array( 'aside', 'gallery', 'link', 'image', 'quote', 'status', 'video', 'audio', 'chat' ) );
After that, I got a menu at the right of my edit/add post page called 'Format' giving me all of these options.
I think this is a bit confusing on the part of WordPress. Granted, if a theme doesn't support displaying all of these different post types, then maybe it makes sense to not show these options by default. But if you're going to hint that they are there and then provide me no way to edit them, I'll just be frustrated.