Overburdened Knight early in the game, how to carry more

There are four main things that help in hording items: getting a bag of holding, keeping a stash, travel improvements, and value assessment.

Bag of Holding

These can be purchased in tool shops and other stores, can sometimes be found lying around in the Gnomish Mines, and there's a 50% chance you'll get one at the end of the Sokoban levels. Refer to this map for reaching the Mines and Sokoban, but simply put they're fairly early. The earlier you get one, the easier everything becomes.

The bag of holding is a container, which automatically expands your carrying capacity. Unlike your inventory which is limited by the number of letters in the alphabet, an infinite number of items can be stored in a container. Of course, an infinite item quantity is an infinite weight, which is where the second benefit comes in that a bag of holding reduces the weight of its contents. An uncursed bag of holding reduces the weight of items by 1/2, while a blessed one reduces the weight by a whopping 3/4!

Bags of holding make it a lot easier to both carry all the essentials you need to survive in the dungeon, as well as traffick heavy goods across long distances. Hope to get one as early as possible. However, there are some dangers involved with what you put into a bag of holding: read up on them here.

Keeping a Stash

It's indeed unreasonable to try and carry everything you can. So what is important is to have a place to safely store your stuff. Keeping a stash often is tasked with a few points.

1. Scare monsters away - monsters that might pick up your stash items can be scared away by either dropping a scroll of scare monster on the stash, or by engraving "Elbereth" onto the ground. Ideally Elbereth written permanently via a wand of fire or wand of lightning. (Since 3.6.0 though, Elbereth only works on the square you are standing on, not on stashes.) So use one of these, or hostiles can do things like pick up and use your weapons, wands, potions, etc, or more dangerously gelatinous cubes can eat all your stuff.
2. Use a container - Not every monster respects Elbereth, and the majority of creatures that don't happen to be the kind that pick stuff up. Storing it in a container prevents these creatures from accessing your stuff. Pick something like the many chests you see lying around. Just be warned that most containers are of an organic material which gelatinous cubes will eat, destroying everything inside - so don't forget Elbereth!
3. Keep in a safe place - Elbereth and containers only protects against creatures themselves, not stray bolts of energy. You want the stash to be in a place that will ideally see no monster activity, or not be in danger of damage. Many people pick the first level of Sokoban, as its monster spawn rate is very low (and the Eye of Aethiopica artifact provides a very quick warp to Sokoban when Invoked). An alternative method is to store your stash in a one-tile room behind a locked door. Also consider using boulders, which block most monsters from accessing it.
4. Keep easy access - Don't create a stash in a remote place if you can avoid it. Instead, try to stash it as close to stairs while still being out of the way of combat. Combine this with mining short-cuts through levels if you have a pick axe or mattock, and it'll be a lot quicker to return to the stash once you have better identification methods.

These are the main points of stashing. All it needs to do is hold onto items and keep them safe.

Travel Improvements

Keeping a stash is worthless if you can't use it! You need to have better methods of travel across the levels. This isn't really limited to hording items, but it's something I can cover as a relevant tangent. Just consider 3 commonly accessible methods of easing your travels (I'm not going to cover the Eye of Aethiopica since it's rather specialized and already covered up above).

• Level Teleportation - One of the best methods to reduce travel time is level teleportation. The easiest method is by reading a cursed scroll of teleportation. Combined with teleport control in some fashion, this lets you very quickly reach the level that your stash is from, and then return to where you need to be. Very risky without teleport control, however.
• Teleportation - Standard ease of travel when moving across a single floor. It can also speed up actually reaching your stash, and then returning to the stairs. Not as risky without teleport control, but can be more annoying and time-consuming.
• Digging - Pick up a pick axe or dwarvish mattock, and just start taking out walls. Convert as many floors to a straight line path from stair-to-stair. The less corridors you have to navigate, the less resources spent. While digging holes to fall is an option, do note that where you actually drop is random so building a complex "down elevator" doesn't quite work as well as it may seem in theory.

Value Assessment

The final point to knowing how to effectively horde items is knowing what to horde. Equipment, such as weapons and armour, are often useless to keep. They sell pitifully compared to their weight, and you rarely need to keep any equipment that isn't immediately useful to you. Also try to figure out the usefulness of items by unconventional means. Reduce not just how much you have to carry, but how much you need to stash as well.

And finally, consider carrying no more than one copy of heavy items like potions when unidentified. Identifying one serves to identify them all, and simply rely on one or more stashes to keep the extras.

Wisdom doesn't affect Searching, as far as I know. So I'll instead cover how you can improve your searching, rather than improve wisdom. The main things that affect it are Luck, having a pair of lenses, and getting Excalibur.

• Luck is the main factor. The higher your luck, the more likely you'll find a door in fewer chances. If you have slightly bad but not horrible luck, you can usually guarantee finding a door in around 20 tries. But if your luck is really bad, it's incredibly difficult to find such doors. So more important than anything, don't ruin your luck. If you have ruined your luck, you should wait for the bad luck to time out before you continue to search.

  To improve your luck, the main options are to throw gems at co-aligned unicorns or to sacrifice monsters that make your god happy. These both rely on the fortune of running into an early co-aligned unicorn and altar respectively. As reinforced by sepp2k in the comments, do note that good luck will time out just the same as bad luck, if you lack a luckstone. Which, early game, is not a very common prospect.

• Lenses are an accessory time item you can wear over your eyes. They're extremely rare, but if you're lucky enough to find a pair early on then you can use them to help, as they improve the success rate of finding secret doors. There is an artifact pair of lenses, but they are Neutral alignment (and the Monk quest artifact, specifically) and so wouldn't be of use to a Lawful character such as yourself. But they are a pretty handy item for Neutral non-monk characters lucky enough to get an early wish that they would like to spend on it.

• Excalibur is an artifact longsword. Any Lawful character who reaches XL 5 can dip a longsword into a fountain and have a chance to get this weapon. As a Lawful Valkyrie, you start with a longsword, which makes this that much easier to get. Plus, it's a great weapon to have in general.

  While wielded, it not only grants the searching extrinsic (which automatically searches at the end of every turn), but it also improves your success rate. Note, however, that the bonus it gives is in proportion to its enchantment level. So if you don't happen to run across any scrolls of enchant weapon early game, it won't help too much. But this weapon represents one of the best early game aids to searching.

If you have good item fortune, then you may also come across a wand of secret door detection or a stethoscope. These items, once you find yourself at a dead end, greatly expedite your success by simply revealing the secret passages. Healers start with the latter.