I want to incorporate hot air balloons as a means of common travel in my fantasy world, but I recognize that hot air balloons aren't really "propel-able". My question is, how would someone hypothetically operate a small airship or zeppelin type of structure in a fantasy world? I'm looking more for answers about balloon-based structures, not a sail based or Stardust-esque flying ship.
You have a fantasy setting and you have magic. So keep the hot air balloon and add a propulsion system.
Based on TheBlackCat's answer you can make a pedal powered engine for your airship by placing a golem in a hamster wheel attached to a gearbox. If you go by the clay golem concept you can make the engine as large or small as you want, by the size or number of golems used. A necromancer could even use undead instead of a golem.
The other option is a possessed engine (As used in Divinity Dragon Commander or even Warhammer 40K) where a demon/spirit is bound to the machine and forced by some pact or contract to operate it.
If you want to skip engines entirely you could simply have a wind manipulating creature or mage direct the craft where it needs to go.
These answers all depend on what level of fantasy and magic you have, but don't require too much.
You could do it just like people navigate hot air balloons in our world: The pilot watches the clouds to see what direction the wind is blowing at various altitudes, and then heats the air or lets it cool to alter his altitude to a place where the wind is blowing in the direction that he wants to go. There are usually enough different air layers that he can find one with the wind in at least roughly the right direction. If not, you're stuck until the wind changes. Much like a sailing ship can be becalmed.
Like see here, http://www.wikihow.com/Fly-a-Hot-Air-Balloon, point 7, or https://www.quora.com/How-do-you-steer-a-hot-air-balloon.
Depending on the type of magic you want to use...
Use a Discworld Axle
In the Discworld novel Thud, Terry Pratchett describes an item known only as an "axle". It's essentially a perpetual-motion machine, consisting of two six-inch cubes joined together on one face, slowly rotating but absolutely impossible to stop. If you have one side of an Axle-type object secured to the body of your ship, and the other connected to a large gear, you can translate that slow rotation into any kind of propulsion you want. A drive chain could run from the big gear to several propeller units scattered around the ship, for example.
Of course, while Pratchett's Axle doesn't require any kind of fuel, you could certainly declare that yours does need fuel. Heroic Axles might need coal or food or a regular spell cast by a wizard to keep running; villainous ones could run off the blood of the innocent.
Fire Spells = Jet engines
A jet engine is functionally a fairly simple device - air is drawn in at the front, compressed, mixed with fuel, and ignited. This causes a rapid expansion of the air/exhaust mixture, which is shot out the back. In a magical environment, you can replace fuel in the mixture with a mage's fire spell. Keep a perpetual flame burning, surrounded by whatever super-strong metal you want and fed by compressors made of a similarly super-strong metal, and you have a decent jet engine. It would probably require regular input from the wizard, of course, so a ship's captain needs to keep his wizard's well-supplied.
Why bother with contraptions, when you can summon spirits of air to move your ship wherever you wish? With the winds at your command, you can simply move wherever you want to go.
Mythology and fantasy are replete with tales of chariots, carts, and, of course, sleighs, pulled through the air by flying animals. Birds are a common choice, but so are celestial draught animals like horses and oxen (and reindeer). Strap a handful of flying animals into a harness and have them draw the flying ship through the air. For bonus points, they provide a) fertliser for the fields you're flying over, and b) an aerial bombardment capability.
In the end, the nice thing about magic is that it can literally do whatever you want; the problem with magic is that it can literally do whatever you want. The only bound is your imagination. Any method you want, you can use. It makes it difficult for us to come up with a solid answer, rather than a lot of opinions. I would strongly suggest that you define what your magic can do first, then let details like how it propels ships flow from that starting point.
If you don't want to use sails, probably the solution most available to a fantasy setting would be pedal power. The principles of both pedal power, the necessary gearing, and propellers were know in the early renaissance. Smaller vehicles could be powered by the occupants, larger vehicles could be powered by horses or oxen.
The next-best choice would probably be some form of steam propulsion. The problem is that practical steam engines would be hundreds of years off from any fantasy setting. Using steam as a power source dates back thousands of years, but the early designs were just toys, they weren't a practical power source. Carrying enough water and fuel to make such primitive steam propulsion practical wouldn't be feasible without magic.
There have been some interesting suggestions. I'd like to add my own five cent:
have your airship pulled by a team of oxen or horses, whenever the wind is unfavorable, and use sails whenever the wind is right.
You might even winch the oxen up in those situations.
Apart from the coolness of having a bunch of hovering oxen, that helps crossing rivers, or all other kinds of hard-to-navigate territory.
Remember that you only have to overcome the wind drag, so this means of propulsion should be quite feasible in most weather situations.
I'm currently writing a book with airships. And what I did is by using balloons filled with "Graphene aerogel" a solid lighter than air, it provides a form of lift that won't get destroyed super easily. Also the ship's use engines (steampunk style, but you could use magic) to propel in different directions. As well as for lift, that way destroying the balloon isn't the only way of sinking the airships.
There was a sort of contemporary fantasy series where one major point were vacuum dirigibles. The material strength (and also the air evacuation) was conveniently produced by rune magic arrays. I think that propulsion was magical, too. Runes were, however, more like engineering (so, anyone could study them, it took a lot of work, but they could be calculated to produce a desired effect, they needed maintenance, too). The world was rather modelled after late Belle Époque.
If you manage to create a material strong enough to withstand the full atmospheric pressure, you'd be able to create very cool airships. But not only them. This technology would also change the life to an extreme degree. Stronger atom reactor shells, really cool bulletproof vests, thin fibers of this material for fun and profit (think: monomolecular thread killers from cyberpunk, but more physically-based), space elevators, insanely-deep submarines and all kind of deep sea exploration, etc. And, of course, planes. Large planes, huge planes, war planes. If you can create a material for a vacuum dirigible, the last thing you do is a vacuum dirigible. Because you are on your way to colonise space or to fight the last war in humanity's history, depending on whom you ask.
Note that you may well want artificial flight for people and some cargo, but if it has quirks/limitations, that may be better for plot than a no-ugly-warts technology. That said, how about:
Natural gas (methane, CH4, molecular weight 16) as the buoyancy-producing gas. Yes, it's flammable and thus a risk of flying.
I further posit that they've worked out a crude method of propulsion, much like that of the Nazi https://en.wikipedia.org/wiki/V-1_flying_bomb#Power_plant. These are pretty simple mechanically, but they need a liquid or gaseous fuel. I posit that they use the lift gas itself because (perhaps petrol hasn't been discovered yet and alcohol and olive oil are too expensive.) So range, especially against or cross wind, is fundamentally limited -- and flight is dangerous, but doable. Have fun!