When the elves of Eregion began to forge rings, their purpose - suggested to them by Sauron - was clear: to construct artefacts which would enable them to build realms in Middle-earth as fair as Valinor. While we don't know precisely what abilities they built into the lesser rings, we do know what the Rings of Power - specifically, the Sixteen (since the Nine and Seven were one set, originally) - were capable of:
Concealing both the bearer and the ring in the Unseen.
Prolonging a mortal's life - though in the end, they would fade permanently into the Unseen.
Generating wealth (if given a starting gold horde to work with).
Granting their bearers power and influence.
Making the bearer desire power, or wealth, or possibly immortality.
Sorcery - though what exactly this means is unclear.
The One Ring, forged by Sauron to command the others, granted some of the same abilities - invisibility, immortality. Since Sauron's purpose was not the same as the elves', however, he didn't include the other powers, instead adding some of his own:
The ability to see the thoughts of the other ringbearers.
The Ring causes its bearer, and others, to desire it.
The Ring is capable of some degree of independant action - such as falling off a finger. It desires to be with Sauron.
Finally, before Sauron completed the One, Celebrimbor forged the Three. These are distinct from the Sixteen, with very different abilities:
Concealment of the ring - but not the bearer.
No indication of immortality being granted.
The ability to maintain a land (Lorien) in stasis.
The ability to augment magical abilities, such as Gandalf's fire spells.
How did the rings accomplish this? It seems clear that the Unseen is a significant component in their magic - and, indeed, it lies at the heart of their power.
To the Eldar, a person consisted of two parts: the body (hroa) and the spirit (fea). The Unseen is the realm of the spirit - thus, Glorfindel, who had lived in Valinor under the light of the Two Trees, burned bright, while Frodo's mortal friends were dim shades.
Since the Eldar had no reason to wish for invisibility, it is clear that this power - the shifting of the physical body into the realm of the spirit - is a side-effect of the rings' operation. It is, in fact, the means by which they gain their power - by shifting the bearer into the realm of the spirit, a ring grants them previously unknown powers over the spirits around them - spirits which they can now see with their normal sight. In fact, given that this is how Ainur (being inherently beings of spirit, unless they choose to be fully embodied, like Gandalf) normally see, the rings can be said to grant demigodlike power through this simple means.
Many of the rings' powers are simply logical consequences of allowing the bearer to directly alter the spirit of things - the world, objects, or other people. Power and influence? No problem, when you can tweak another's soul to do your bidding. Wealth? They may simply be able to duplicate an object - but even if not, it's easy to get money when you can influence others so much. Even understanding other languages can be explained as a result of looking directly into someone's spirit - and, indeed, Galadriel tells Frodo that he can see much of her thought.
As to where the rings get their power - that comes out of the other two abilities. Each ring bonds strongly with its bearer, in fact tying their lives together - the spirit of the bearer, and the spirit (of whatever kind - creating this spirit and binding it to a piece of metal may be the true art of ringmaking) of the ring. The ring is then powered by its bearer - and specifically, by the desires of its bearer. To ensure they are constant powered, they also enhance these desires.
Sauron, wishing to corrupt the elves, trained them to make the rings respond to, and amplify, their bearers desire for power, or wealth, or other gifts the rings can grant. This would not be a bad thing, he no doubt argued - after all, we want them to be used! When he came to make his own Ring, however, he changed the programming (or whatever) a little. He didn't want to have desires thrust on him by the One, after all - so he programmed it to respond to desire for itself. Since he never planned to take it off, this would hardly be an issue.
The immortality effect of the rings comes through this binding: if your life is tied to a piece of metal, you cannot die until it is destroyed. Sauron, not planning on letting his Ring go, permanently fused part of his spirit with it - other ringbearers simply refuel it on a constant basis. And the fading? It appears that making the transition to the spirit realm and back is a 'lossy' process. Each time you transition, a little less of your physicality makes it back through...
Of course, as we know, the Sixteen were thoroughly corrupting: desire turned to obsession. Among men, it led to power-grabbing immortal kings who later became Nazgul. Among the dwarves, it led to great hordes of gold (though it seems that, the bodies and spirits of dwarves being fundamentally different to those of elves or men, they were granted neither immortality nor invisibility). And it is this latter which may have suggested to Celebrimbor that something was wrong: he is said to have given one of the Seven directly to Durin III, and may have witnessed the beginning of the gold-lust.
And so, when Celebrimbor forged the Three, he introduced some changes. The Three do not carry their bearer with them into the Unseen - they move themselves, and thus act as a conduit, weakening the powers they grant, but protecting the bearer. The corrupting wealth-and-power abilities were entirely removed - with regret, no doubt, but they were too much of a danger. In their place was added a different method of building and preserving elven kingdoms: the ability to link the ring's power, its spirit, to another - be that another person, or a part of the landscape. Thus the bearer could no longer desire anything for themselves - the desire that fuelled the ring was the desire to help someone or something else, by granting it extra power. To Galadriel, this meant preserving Lothlorien in time. To Gandalf, it meant comfort - and linking the ring back to his own inherent abilities, enhancing them. To Elrond... well, the books never say directly, but the time he obtained Vilya is also the time he became a healer - could he have used its power to grant strength to those weakened, and give their bodies a chance to recover?
"Three Rings for the Elven-kings under the sky/ Seven for the Dwarf-lords in their halls of stone/ Nine for mortal Men doomed to die/ One for the Dark Lord, on his dark throne..." - The Rhyme of the Rings