You gain four points for each experience point you gain from killing monsters. Once you reach 500XP (250XP for a wizard), you can be certain that you've left beginner status, assuming you haven't gained or lost XP or levels by methods other than killing monsters (consulting the oracle, quaffing a potion of gain level, etc).
Once you've reached level 7 (level 6 for a wizard) you will have almost certainly gained enough XP to reach 2000 score points (1000 score points for a wizard).
I've finished my game for the wizard so I can outline the strategy which was working for me. I don't know what parts you know exactly, so I will tell you everything I consider important.
First of all, dump your quarterstaff and try to use daggers as your main weapons. They can be not only wielded, but also thrown, and if you become skilled in using daggers, you will be able to throw several daggers at once. Ten daggers or so is a good number to start with. Also I'd find an armor which doesn't hinder spellcasting (like studded leather armor) and try to enchant the cloak. Obviously enough, you should try to learn as many spells as possible and get all the resistances you can.
I advise not to go into the Gnomish Mines when you find the entrance. You can reach the Minetown easily, but you won't be able to reach Mines End yet and get out safely. So instead of going to the Mines, go to the Oracle and then to Sokoban. Sokoban should train your strength because you will move boulders a lot, which is helpful, and also you will get some gold and a gift at the end, which is, as you probably know, either bag of holding or the amulet of reflection.
After Sokoban you should go to Minetown and try to reach Mines End. Minetown has an altar and if you're lucky, it will be your god's altar. If that's the case, you should offer corpses of recently killed monsters to your god until you get Magicbane. This is a magical dagger, which is extremely helpful in combat.
Mines End will give you a luckstone (and also some gems). You have to fight a lot of monsters there though, so stand on the stairs and use Elbereth to keep them off. If you have Magicbane, engraving done with it will be harder to erase.
If you have survived Mines End, you can return from the Mines to the main branch and safely descend until you come to the level with the quest portal. Don't worry, if you haven't reached level 14, the first quest level usually has Wraiths whose corpses raise your level when eaten. If you still need to gain levels, descend lower in the main dungeon. Usually I don't linger in the level after I have explored all the passages. You should aquire necessary level before you reach Medusa's island.
When your level is enough, you can finish your quest. Your nemesis won't be tough if you know how to hinder his healing. After you finish him, you get your quest artifact which replenishes your power, and later on you shouldn't have any problems.
That's the basics of the wizard strategy.
Best Answer
There are two parts to the hunger problem in NetHack: gaining nutrition and reducing nutrition loss.
Under normal conditions, each turn, you lose one point of nutrition. You start with 900 nutrition, and start feeling hungry when you drop below 150. At 0, you'll faint. Starving to death happens at a negative value based on your constitution.
Nethack is a very complex game, so there are exceptions to most of the guidelines below, and other, more obscure ways of sustaining yourself, but these general principles are good guidelines.
Gaining nutrition
Comestibles. The most straightforward way to gain nutrition is to eat comestibles (labeled as
%- food, meat and corpses). The amount of nutrition you get depends on what you eat. Early on in the game is often the riskiest time; you may not start with much food. At this stage, it's normal to eat as many fresh, safe corpses as you can get your hands on. If you make it that far, there is guaranteed food in the Sokoban levels, which are accessed somewhere between levels 6-10.Praying. Praying while weak will restore your nutrition, but safe use depends on your current prayer timeout. Also, using up your favour with your god could backfire if you have a sudden unforseen need (e.g. you have gained a fatal illness like food poisoning, or are being turned to stone).
Convert boulders to food. As theist points out, you can convert boulders to huge chunks of meat if you have the stone to flesh spell. These are hugely nutritious (2000 points).
Reducing nutrition loss
Wear a ring of slow digestion. This is a great item, if you can find one. It changes your rate of nutrition consumption to 5% of your normal rate (giving you twenty times as long to find food). As Grace Note points out in the comment below, this is because you are only paying the nutrition cost of the ring - your standard rate of consumption is halted.
Take off your rings. In general, you lose one nutrition every twenty turns for each ring or amulet you wear. Rings of regeneration are particularly pernicious; if you're wearing one, you'll lose a point every other turn.
Drop your stuff. If you're Stressed or heavier, you lose a point every other turn.
Don't cast spells. Spellcasting makes you hungry (unless you're a wizard with high Intelligence).