Saturation simply means that an increase in base current results in no (or very little) increase in collector current.
Saturation occurs when both the B-E and C-B junctions are forward biased, it's the low-resistance "On" state of the device. The properties of the transistor in all modes, including saturation, can be predicted from the Ebers-Moll model.
No, it's the collector current that is dependent on the base current, not the other way around. No matter what the collector current is, the base current is \$\dfrac{V_{MCU} - V_{BE}}{R}\$.
Keep in mind that \$V_{BE}\$ will be twice the value of another transistor, as there are two junctions between base and emitter.
But it's true that the collector current is what you want in the end. So to find the resistor value (don't just pick 1k), you calculate \$I_B=\dfrac{I_C}{H_{FE}}\$. If you want \$I_C\$ = 2A and \$H_{FE}\$ = 400, then your \$I_B\$ will have to be \$\dfrac{2A}{400}=5mA\$. This is a value your microcontroller will be able to deliver, but always check the datasheet.
To put it all together, \$R=\dfrac{H_{FE}}{I_C}\times (V_{MCU} - V_{BE})\$.
edit
Olin is right about the resistor value being the maximum, i.e. the base current being minimum. For many parameters in a datasheet you'll find more than one value, like typical and maximum or minimum. You should always calculate for worst case conditions, and it may require some logical thinking to find out whether worst case is minimum or maximum for a particular parameter.
Take \$H_{FE}\$. In my example I picked a value of 400. As higher is usually better datasheets often mention a minimum value. What if it's higher? The base current won't be different, so the collector current will be higher. If you drive the transistor in saturation \$I_C\$ will no longer be determined by the transistor, but by the load's impedance will be a limiting factor. So, while the transistor would very much like to draw a larger collector current, it won't change. So you think you're safe; the minimum specified \$H_{FE}\$ is fine, higher is still OK. There's something else to consider, however: \$H_{FE}\$ is not constant, it varies with \$I_C\$, and the datasheet should have a graph for this. So check this for the wanted collector current.
\$V_{BE}\$. Two PN junctions, so that's 2 x 0.65V = 1.3V. Olin found that a 300\$\Omega\$ base resistor should be fine, in fact leaves some margin. But when I look at the datasheet for the TIP110 it says \$V_{BE}\$ may be as high as 2.8V! That would result in a base current of \$\dfrac{3.3V - 2.8V}{300 \Omega}=1.7mA\$, and that's too little to get the wanted \$I_C\$ of 2A: \$400 \times 1.7mA\$ is only 670mA.
You're getting the idea. Don't simply use typical values, but make sure that your circuit still works with components with extreme parameter values. This is not so much of a problem with projects where you only build 1 device: you can see what's wrong and adjust. For production you have no choice: always design for worst case.
Best Answer
Read the datasheet more closely : there will be conditions attached to that spec for a minimum hFE. One of those conditions will be that Vce is greater than some voltage : probably 2V. (Just checked the datasheet; actually Vce=5V). When you are trying to saturate the transistor, those conditions obviously no longer apply. Instead, as Vce approaches Vce(sat) hFE decreases quite dramatically.
Note that the actual base current and hFE will vary for Vce(sat) - you might find hFE=25 at that point for a particular transistor and a particular current Ic, or alternatively at hFE=10 you might see Vce lower than the rated Vce(sat) - the datasheet Figure 2 shows Vce(sat) around 0.05V for a useful range of currents! But these are the figures guaranteed by the makers for all their transistors.