1. what is exactly rpm?
2. where is it likely to get stored?
3. is there an rpm associated with each and every software?
1) rpm can mean two things: a program for managing software packages; and software packages made in order to be managed by rpm program.
2) It will be stored on your local computer in 'suitable places', i.e. all the files go into the right places. Extra information (e.g. which packages are installed and what they contain) are stored in a special place (look 'man rpm' in order to find out the exact place).
3) NO. And probably never will be. But there are definitely rpm-s for most of the software an average computer user will need.
So, it you have an RH box, I definitely recommend to install rpm (package manger) and use rpm packages whenever possible. The main alternative is to compile the packages yourself, but it is a slow process, it is not so easy to remove compiled packages, and sometimes it needs a bit technical knowledge. Of course, compiling gives you much more freedom.