From observations, there are even more petrol stations in Bulgaria than in, for example, Sweden. The main reason is that the market is not as consolidated as in other countries, and among a handful of prominent gas station chains (Petrol, Shell, Lukoil, OMV, etc.) there are also a number of local gas stations as well. Gas stations are also spread out in the cities and you won't have to go out of your way to refuel.
However, in remote areas (for example, mountain regions in Bulgaria), you should make sure you have enough fuel for at least 30-40 km. But you'll never have to worry about this in cities, smaller towns and on main roads. I don't think you have to take any special precautions that you won't normally take to make sure you don't run out of fuel. Most GPS vendors have maps for Eastern Europe that would list pretty much all major gas stations.
That being said, I'd usually avoid unknown gas stations in some isolated regions, as the quality of the fuel cannot be guaranteed.
On the main roads, highways, in cities and larger towns, there will be for sure some big-name stations that are opened 24/7, and the others are mostly opened around 16 hours daily.
Note also that there are no self-service gas stations in Bulgaria.