This game is really fun, but I'm not entirely sure how to heal. The only method I've discovered so far is to rest, but that is usually interrupted/results in my items getting stolen. Are there any other ways to heal besides that and how do I prevent these things from happening when I try to rest outdoors?

In the new update cooked food seems to be the best way to heal while outdoors, it applies the "Rejuvenation" buff, which slowly regenerates health. You can increase buff duration by having a higher Charm score, making Delightful meals (the ones made by cooking flowers) heal more than other types of meals.

There's a class that doesn't get encounters while resting outside. For other classes if you don't want to risk getting ambushed you should be inside a building with a closed door before resting, if you have a bed and a source of warmth (braziers, for example), your resting will be much more efficient.

Other than those two, if you get lucky with runes you could infuse your weapon with water, the healing from water runes gets amplified by a certain Curio you can get from "Tool Boxes", and it maybe also scales from attunement, but I'm not sure. Or if you get a rune of rejuvenation, combine it with a self-cast spell to have easy healing everywhere you go, the same rule for charm that I wrote above applies here.

Thanks for the info!