You can measure with a μC the voltage of the battery which directly powers this μC (without a voltage regulator). You need to have a reference voltage, which doesn't change as the battery voltage changes. The idea is either to measure the battery voltage w.r.t voltage reference, or to measure the voltage reference w.r.t battery voltage. Many μCs have a built-in voltage reference, which can be enabled from software. Some μCs can output a reference voltage to a pin. An external voltage reference would work too.
To conserve battery charge, you can use the μC pin to turn on the battery voltage measurement circuit only occasionally. Here's one of the variants of the circuit.
Which topology to use depends, in part on which type of the μC you're using. (?)
You might find that sensing battery voltage is not an accurate enough way of sensing the remaining capacity. In portable equipment (cell phones, laptops), battery capacity is estimated by measuring current in and out of the battery. There are dozens of specialized battery fuel gauge ICs (bq27200, for example), which help with this task.