Cort said: it took us 3.5 billion years to go from single-celled creatures to land plants. That would be the upper bound on this process.
Which is not precisely true. It is one upper-bound on evolving a solution. ie: one data point. It may take a lot longer than that if you want to evolve solutions; perhaps Earth is on the fastest of all possible evolutionary paths.
Anyways, the point is: you're not evolving anything. You're taking already evolved solutions, and selectively inserting them.
Dronz said: with imported/engineered microbes pre-developed on Earth, might be much faster than what evolved naturally out of the primordial ooze.
Precisely.
You're probably going to want to start with some monitoring. Did the planet you select already have life? You'd said you wouldn't know what you've got until you get there - it might be considered a hostile act to come in with an automated probe and try converting someone else's planet :) Besides the ethical considerations of eliminating life that's evolving itself (depends on your society's ethical constraints).
You'd probably want at least a decade to see what types of climate variations you're going to get from orbital perturbations, as well as a study of the star - some of the star's output can be analyzed from afar, but some may need in system analysis. This may determine what life you want to seed to moderate effects that exist in your system. You might be able to skip this, and play catch-up when you get surprised by events. But that will lead to increased failure rates.
I'd give it a century of study, if you've got time to burn.
The biggest thing, besides being in the habitable zone, having roughly Earth-like mass, and a carbon-dioxide atmosphere, is having enough liquid water.
Liquid water is going to get you a chance to get your autotrophs and cyanobacteria started. Which will start getting you organics from inorganics and an oxygen-based atmosphere. Once you got those started, introducing something with chloroplasts (algae most likely) is going to be the big thing - you want your Great Oxygenation Event to happen ASAP. Time-scale on that is unknown, and may depend on conditions. But you're going to want your autotrophs to have had some time to work. How many are you seeding initially? Are you setting up reactors to make tons of them in orbit? Or just injecting a nanoliter (microliter?, milliliter?, liter?) worth of them in selected spots (how many spots?).
Turning over your atmosphere into the ocean to get the CO2 out and O2 in, is going to be a thing. It's a pretty complex field of study. One key driver is do you have polar ice caps (or, can you make them?)? That drives thermohaline circulation, and will take a ton of CO2 into the ocean (although with a primarily CO2 atmosphere, the ocean may already be saturated...). Iron is a limiting nutrient, and if you've got the tech, pulverizing nickel-iron asteroids and drifting the dust down on the oceans (or dispersing from flyers) may greatly speed up your algae/oxygen production.
http://benmatthews.eu/benphd/chap1.html For a lot of info on Earth's exchange, ie: not exactly what we're talking about - but we do 92 GtC in and 90 GtC out in our oceans.
Once you've got the ocean / atmosphere work started, you're going to want to start on the land-mass. Cyanolichens and lichens are what you want to start breaking down rock to get soil, and to put the organics into your starter level soil. You can be dumping these on any rocks. No dams necessary. In fact, without plants respiring, you may not have a lot of freshwater to be working with, once you get inland.
At phases in here, you're going to have to choose some types of lifeforms to manage cloud seeding / cloud-cover and albedo. You're going to need some satellite coverage and computer monitoring to figure this out. This is going to require some pretty robust computer programming, or a human that's in and out of stasis once a year/decade. I'm assuming you're not sending humans, since the cheapest way to do this is to send something the size of a football with DNA codes a fabricator, and some expandable vats (it'll collect shielding in-system, to
protect from flares/gamma rays).
This is about as far as you can (easily) go with a football. Your probe would have to be able to vastly expand itself in order to make tons of seed, and/or animal life. You might be able to store some insect life, and micro-shrimp / fish eggs - but you're probably looking at something more the size of a room - and you could easily fail the insects and fish if you are carrying too few eggs. Your first set(s) may be put down too early, and all fail because of not enough supporting substrate. Any time you drop eggs, expect to lose some of the drops because of errors / bad placement. You can take plant seeds with you, but like the animals, you'll have a tough time taking enough to make a big dent soon. Best bet is to set up an automated farm in orbit and harvest seed. This is going to make your probe a lot more complex.
Anyways, once you get some organics in the soil, then you're going to want to go with some plants. A lot of seeds, and little return to start with. You'll want stuff that handles aridity and low-to-no soil. Once you've given that some time to work, and maybe get a freshwater cycle setup, then you can think about insects and other stuff.
You can probably have seeded the ocean with fishes prior to this.
If you've got fishes, you can move rapidly up to birds and mammals which hunt fishes, and some herbivores. Landing those from orbit is going to be a trick. A lot of the other stuff can be dropped with a heat-shield / cooling apparatus and a micro-chute, and let it bounce. A mammal or a bird, not so much. Training your bird to fly in orbit... also tricky. You're not going to drop bird eggs, unless you're also dropping incubators. You may need robot mothers to teach some skills.
Scifi: The Forgotten Planet is a story of terraforming gone awry.