First you need to clean the wall thoroughly. It's always a good idea to clean your walls prior to painting because they pick up grime over time which will prevent the new coat of paint from adhering properly. In a kitchen, stains are more likely to be caused by splashes from food, so they could be greasy so it's even more important to clean first. Use TSP (tri-sodium phosphate) soap if you can find it; if not, there are enzyme-based substitutes that you can use which are OK.
You should sand the old primer, but not enough to remove it from the wall. You only want to roughen the surface so that the new primer has a better surface to hold onto. Make sure to wear a dust mask while you're sanding. Rub the wall lightly all over with sandpaper or a sanding sponge (which I use because they're washable and re-usable). You should see light scratches on the paint.
After you sand, be sure to wipe down the walls with a damp cloth to remove any dust from the sanding.
Finally, look for "stain-blocking primer". Make sure that the primer you choose will work with the type of paint -- oil-based or water-based (aka latex paint) -- that you're going to put over it. I've used Kilz to good effect; other people on this site recommend Zinnser Bullseye 1-2-3