Exalted Companion is the easiest way, lets you turn any normal animal companion into a celestial creature and thus a magical beast.
edit: also, Ghostwalk has a spell to raise an animal companion as a ghost iirc, and even with ghostwalk ghosts being a bit odd that's still a type change (though to outsider instead of undead)