Horsehead
The shield and jump spells will aid you here. Shield will substantially reduce the damage inflicted by the boss' mace attack, while jump will make it easier to target the creature's weakpoint. Simply jump and thrust at the boss' face to land a hit. Try moving away quickly, as it will usually counterattack if you come close to it.
Helmethead
Like the horsehead strategy mentioned above, you will need to do a few jump and thrusts to the boss' head. However, each blow you land will usually cause its head to fall off and float around the room, firing projectiles at you. Since the boss repeats this pattern, it's recommended that you get close and attempt to land as many hits as quickly as possible.
Horseback Ironknuckle
This battle has two stages: horseback, and on foot. If you obtained the downward thrust from the dragoon in Mido, then defeating the horseback form will simply require a few downward blows to the horse's head. Otherwise, try using a few well-placed jumping thrusts to the horse's face while the boss is stationary. Once the horse is defeated and the ironknuckle begins to persue you on foot, try a few jumping thrusts to the boss' face to land easy blows. Note that altough knuckles are usually guarded against melee attacks, jumping and then landing blows to the face will usually target their weakpoint.
Carock
If you did not obtain the reflect spell from Darunia earlier, you will not be able to defeat this boss. (rescue the lost child from the same island where the palace is located to complete this sub-quest and procure the spell) To damage the boss, you must first cast the reflect spell on yourself to enhance your shield with deflective abilities. Then, duck and face the boss when he launches a magic spell at you -- your shield will reflect it back to the boss, damaging him in the process. Note: to make quick work of this battle, you can usually stand in either corner of the room, duck down and remain stationary while the boss defeats itself. The boss usually will not appear too close to these areas of the room.
Boss Gooma
As with the horsehead and helmethead strategies, you must use a jumping thrust to defeat this boss. However, his mace has quite a long range, and moving out of reach can be difficult in this case. Casting the jump spell can aid you in quickly leaping out of the mace's path.
Barba
Barba will generally appear from any pitfall and breathe fire in your direction before bobbing back down into the lava. You may only damage the boss by striking its head. This can be done by either thrusting at it as it rises from the lava, or using the jump spell to reach the boss after it has risen from the lava. Be careful not to be knocked into one of the pitfalls, as a single hit from Barba's breathe attack can easily push you backwards just enough to fall off the narrow ledging.
Thunderbird
If you did not obtain the thunder spell from Old Kasuto, then you will not be able to defeat this boss. (collect all magic upgrade and speak to the old man in Old Kasuto to procure this spell) Start the battle by casting the thunder spell. This is reveal the Thunderbird's face, which is its only vulnerable point. Note that you should be sure to have sufficient magic before entering into this battle. If you cannot cast the thunder spell, then you will only be slain.
Cast jump and attempt to target the boss' face while avoiding it fire attack. If you have additional magic remaining, the shield spell can also help here, as the boss' fire attack inflicts a lot of damage.
(note that you can freely save the game after defeating this boss by using the UP + A trick, and the boss will not appear the next time you enter the palace)
Shadow Link
Link's shadow can be fairly easy, or extremely difficult. Attempting to fight fair with the boss will prove incredibly difficult, as it remains shielded against most of your attacks. Alternatively, you can try ducking in the left corner of the screen and continuously thrusting your sword. This tends to make piercing the boss' defenses a lot easier.