OK. In this case
1) You need to create a destination zone for New York state. For that you should go to the 'Store setup' > 'Countries, states and zones' > 'Zones' area in admin area. In default package, it is already created and it is called 'New York area'
http://awesomescreenshot.com/0df39fbtcb
2) Then go to the 'Store setup' > 'Taxes' > 'Sales tax' section in admin area and create a tax rate by clicking 'New rate' button there
http://awesomescreenshot.com/0b439fci03
3) Define tax rate as follows:
http://awesomescreenshot.com/0ed39fd95f
4) Check checkout section and make sure that everything works fine:
New York state has tax rate:
http://awesomescreenshot.com/0a839ff052 (I must note that your zipcode must me 101xx or 102xx in order to fit pre-defined New York area)
California state does not:
http://awesomescreenshot.com/0ed39fdv1f
Hopefully, it will help.