Where are new contacts stored on iOS? I have two Google accounts linked with my iPhone: home and work.

When adding a new contact in the Phone app, where will iOS store the new contact? I'm not given a choice of which Google account it should use.
You can set which default account it should use to store your contacts. Go System Preferences -> Mail, Contacts, Calendar -> scroll down to the contacts sections and set the Default Account