Microscopic life, especially bacteria, would be simple. We could simply drop off a wide variety of samples on a planet (especially extremophiles) and wait a few billion years. It would probably cost roughly the same order of magnitude as getting a satellite to wherever it is that you want to seed life. This assumes that the planet isn't entirely hostile to even extremophiles.
And it assumes that we can build a container that can supply them with nutrients and their preferred temperatures, for decades or millenia. Alternately, it assumes they can survive the absence of those things for decades or millenia.
But to me the real "should we?" is because it might destroy evidence of other events. Maybe there are simple organisms hiding somewhere or some poorly understood phenomenon that would be obscured or destroyed by our introduction of life.
A more advanced probe would have AI that could study the target planet as it approached and get more accurate readings on the environment. If no evidence of life is present then the AI could begin to rapidly evolve the seed organisms toward fitness for the detected target environment.
On arrival it could orbit the planet for a as long while continuing to evolve and release new generations of seed candidates and observing changes in the environment. Once evidence that life has taken hold is detected it could stop seeding and just continue monitoring. I'm assuming it would send progress reports home every once in awhile, even if nobody was still here to receive them.
What if the ONLY reason humans are worth it to Gaia/life/Earth/etc is the ability to seed life on other planets? What if we're Gaia's reproductive system, the whole reason Gaia puts up with our massive extinction-causing existence?
Imagine a hundred worlds all with life forms subject to evolution.
Basically two ways of that life growing past its planet: 1) A lucky asteroid strike or other outside event 2) A form of creature that can build tools to get out of the planet
Only #2 would have an inbuilt strategy for galactic survival.