CareerCup

Divide and conquer is a good stategy here.
Get the # of gas stations from each state and add them.
Each state can subdivide its seach to districts and so on

Well you can use order of magnitude estinations.
First I assume that per person in the US 10 miles are driven 10^1
Next I assume that the population of the us is >300 10^9 (I round up from 10^~8.5)
Using this I estimate that each day 10^10 miles are driven
I assume average fuel consumption is 10^1 miles per gallon
Now I can say that cars use 10^9 gallons
I assume the average fuel tank is 10^1
I can guess that there are 10^8 refills per day
I assume that a gas station on average services 10^3 cars
My estimate is 10^5 gas stations in the US.
Afterwards I looked it up and it's 121,446 so I did pretty well.

From the US census you can look up what is the average density of gas station / population ( some number ). Multiply that by the population and you get the answer.
10 gas stations / 1000 people * (300,000) = 3000 gas stations. Although this answer will be within the standard deviation and you will have to find the upper and lower limit
+- std.dev.
Another way would be to do data mining. Either way you need some information, you cannot pull a number out of thin air. Well, unless you travel through each and every street and corner of the country.
Another great idea: gather telephone books from each and every area of the US and count the number of gas stations in each region and add them up. Not all gas stations are labelled gas stations.
So, pick and choose, or maybe another idea!!

I would query the foursquare db for such information and also compare with waze db to have a more accurated result.

I will GOOGLE it.