For the My Documents folder, there is currently no way to search unless maybe if you root it. Very hopeful that they will change this soon via an update. Tons of folks on the BN discussion boards want it, so lets hope they are listening!
The lack of organization for my side-loaded content is pretty much the one thing I am not liking about nook. For the moment, I'm just not carrying a full library on my nook.
I am glad you can at least search the BN library. At the rate I'm accumulating free classics, that's going to be useful soon.