How to start with a brand new battery?
AFAIK, there's no special procedure for a new MB/MBP battery. I recently replaced my MBP's battery myself, and searched Apple support documents for care instructions, but I couldn't find anything other than the standard "drain it once in a while."

Btw, my new battery was completely discharged, and it took about 12 hours to fully charge it. I left it on charge overnight and started using the MBP as usual the next day.