I called one gas station in New Jersey who told me it is illegal to
give gas prices over the phone. Can someone confirm or deny this - if
so please explain the "law".

The topic of giving gas prices over the phone is discussed here:
http://tinyurl.com/b5n7c

I don't know about New Jersey but I used to manage a gas station in
Indiana and at no time were we ever told that giving gas prices over
the phone was illegal. It "may" be against company policy to do so
however because they may give one price on the phone and when you
arrive the price may have changed leading to conflict at times.