I’ve heard that some people use organic (no pesticide/fertilizer) potting soil under the sand in their tanks to give the plants a boost. I’ve never tried it, though I am considering it for a future project. Do use caution with some plant species, though. Java ferns, for one, don’t like to be buried much if at all (they get nutrients through their leaves, and the roots are just to anchor them).
Some plants I’ve had success with without fertilizer are Java fern, cryptocoryne, anubias, and “lucky bamboo”. More recently, I have been trying out asian liverwort (sometimes called pellia) and water sprite. Both of those are doing well so far, but then again, I’ve only had them for a couple weeks.
As far as I can tell, good lighting and possibly CO2 (depending on your plant choices) seem to be more important than adding fertilizer.