Pokémon Bank is a new 3DS application and service, to be released shortly after Pokémon X & Y, that allows you store Pokémon online. Poké Transporter is a related application that allows migration of Pokémon from Generation 5 games to Pokémon X & Y.
Pokémon Bank is a standalone application that accesses the data from your Pokémon X & Y game card (when in the 3DS) or the download version. You can move Pokémon back and forth between Pokémon X & Y and Pokémon Bank.
Pokémon Bank has 100 boxes, allowing up to 3,000 Pokémon to be stored privately. Pokémon are stored online, on Nintendo's servers. Due to this, Pokémon Bank will be a paid service. Pricing for US/Europe has not been confirmed but for Japan it will be ¥500 per year, which is about $5 or £3. There will also be a month's free trial.
Pokémon Bank makes it easier to transfer Pokémon between games. If you have both Pokémon X & Pokémon Y, you would need two 3DS systems to trade between them. With Pokémon Bank you can simply upload Pokémon from one game to the Bank then download it onto the other game. Pokémon can be transferred an entire box at a time.
The Pokémon Bank application also has many features to search for Pokémon, sort and filter them.
Pokémon Bank appears to solve the issue of restarting your game. You can deposit your Pokémon in the Pokémon Bank, then restart your game and withdraw them back out again. Any Pokémon left on the game card will be deleted, as is normal. Note that Pokémon are only ever in one place at one time (although the official site is confusingly worded and implies if you lose your game card you can get all the Pokémon back, which is unlikely).
This also implies that it's possible to restart the game multiple times to collect all the starters. You may have to reach a certain point in the game before being able to use the Bank, but since it is a separate app rather than a feature of Pokémon X & Y, that is unlikely.
Poké Transporter is another separate 3DS application related to Pokémon Bank. It functions in much the same way, but for Pokémon Black, White, Black 2 and White 2. The major difference is that Pokémon can only be migrated one way from your Gen 5 game to the Pokémon Bank storage. From there they can be transferred between Pokémon Bank and Pokémon X & Y as described above.
Only Generation 5 games have been mentioned, so it is unlikely that Pokémon from Diamond/Pearl/Platinum/HS/SS will be able to get transferred directly. It would be more work to support older games. Pokémon can be transferred from Generation 4 to 5 relatively easily.
The system also protects against hacked/generated Pokémon.
The diagram below shows the relationship between the various apps and games: