The battery is a voltage source, meaning it has a constant voltage and can provide any current to maintain that voltage. In terms of charges, it will push positive charges out of its positive terminal and negative charges out of its negative terminal (knowledge of the sign of the electron doesn't matter). The capacitor is a barrier to their movement so excess charge builds up on the plates. Positive charge accumulates on the plate connected to the positive terminal of the battery, and negative charge accumulates on the plate connected to the negative terminal.
What's actually happening is that chemical reactions strip electrons from some atoms on the negative side, push them out of the battery, through the circuit, and add electrons on the positive side. Charges are created, but for every negative charge created, there is also a positive charge, so net charge is conserved. When the electrons come to the capacitor, they accumulate on one plate, making it negatively charged. This negative charge pushes the electrons on the other plate away, making that plate positively charged, and those electrons are the ones absorbed by the battery on its positive side.