It isn't clear whether the idea of the magnets was to hold the two hearts together, or these were two cute "refrigerator" magnets. But it sounds like the magnets, themselves, were adequately strong to do their job; the only problem was keeping them attached to the wood.
Those magnets are molded as a flat strip. They're a bit flexible in a long strip, much less so in a short piece, and they want to return to flat. Whether they were attracted to each other or a metal surface, the magnets were flat when in contact (it's the only way they have enough attraction to hold any weight).
They were attached to the wood with double-sided tape designed for attachment to a flat surface. The hearts aren't flat. So the magnets were always trying to pull away, and the tape stuck to the wood better than it stuck to the magnet.
If you glue the magnets tightly to the wood, they won't hold the weight because the whole magnet won't be in contact with the other surface. Attaching the magnet to the wood needs to be done with the magnet flat and something filling the gaps and contours between the magnet and the wood.
If you do it that way, the adhesive will need to bond to both surfaces enough to support the weight of the wood (not much), and tugging on it to pull the magnet off the metal surface it's stuck to, but it won't need insane, super strength. An adhesive that's a bit flexible will do better than one that dries hard, and it won't need as much adhesive strength.
- Elmer's wood glue (Joel Huebner's suggestion), won't stick well to the magnet long term, but it might be a strong enough bond for this lightweight purpose. But it would probably suffer from the same problem as the original sticky tape. A thick layer could fill the gaps, but it shrinks a lot when it dries, so either it would distort the magnet or pull away from it.
- Thick super glue, also suggested by Joel, will fill small gaps, but is brittle, so it would be susceptible to breaking again. There are rubberized super glues that fill small gaps and remain a bit flexible. They would probably work but they're expensive, and overkill for a lightweight requirement.
- Epoxy, mentioned by SF and Matt would probably work, but is overkill for a lightweight requirement.
- Sugru, mentioned by Stephie, would probably be a good solution, but the stuff is expensive.
- A cheap alternative would be a layer of silicone caulk thick enough to fill any gaps when the magnet is flat.
- Going back to how the magnets were originally mounted, they really just used the wrong tape. There is heavy-duty mounting tape that consists of a thick foam ribbon with aggressive adhesive on both sides. The adhesive will stay stuck, and the foam adjusts to the irregularities in the contour.
- Of course, SF's suggestion of attaching a strong, small magnet with a screw won't come off. If you're going to drill a pilot hole for the screw, just drill a larger diameter, shallow hole, and glue in a small, strong magnet for fancier appearance.