Frequency depends on how "fast" the fertilizer is. If it's slow to break down, you don't need to apply it very often, and it's less likely to burn (from too much nitrogen at one time) - so unless you're trying to grow giant pumpkins or something, slow is better, IMHO. Even with slow fertilizer you can apply it more often than you are. Whether you need to depends on what's in the soil already.
I prefer a "balanced" fertiliser, e.g., 10-10-10 - not something with lots of nitrogen.
I also rely on other soil amendments - composted manure, turned-in winter rye, and my own yard compost, in widely varying amounts. These are applied once a growing season. If I had to choose only one amendment, it would be store-bought composted cow manure. These amendments improve the soil structure, in addition to providing slow-release nutrients, and thus are a lot more beneficial than chemical fertiliser.
Yes, you can apply fertiliser over mulch. Some of the nitrogen will be lost to bacteria breaking down the mulch.
In general, just experiment cautiously and observe carefully how your plants react. If you over-fertilise, you'll see some immediate tell-tale yellowing or wilting.