In Ultima 1 and 2, there is no healing in the sense that you are probably used to. Basically, HP is like experience, gold, and food; it's something you earn through your adventures, not something that starts out full and goes down from there. There is no maximum HP stat (I think many versions of these games limit you to 9999), and as a result, there isn't such a thing as "fully healed" in these games.
To increase your HP in Ultima 1, there are 3 options:
1. Purchase HP with gold from a king. The cost, I believe, is 1 gold per hit point.
2. Leave a dungeon after killing at least one enemy. The hit points you gain are proportional to the experience you earned while in the dungeon. (When starting out, it is actually best to go into a dungeon right away instead of fighting on the world map; this is the main reason why.)
3. Rescue a princess; this gives you 1,000 HP if you are able to do this. You will eventually need to do this, but right now you probably aren't ready.
Yes, these games were made when CRPGs had yet to establish their conventions, and as a result, these games do certain things differently from how you would expect. It's not until Ultima 3 when you start seeing mechanics such as a Maximum HP stat, MP, and healing magic, for example.
Bookwyrm627: Go into a dungeon, kill things, then leave the dungeon.
If I recall correctly, when exiting a dungeon, you get hp based on how many things you killed while inside. I don't remember whether quality of monsters matters.
I *think* it's twice the XP you earned while in the dungeon. (I am pretty sure it is proportional to the XP you earned.)