Pokémon Generation IV (Platinum, Pearl, Diamond): What's new since Gameboy versions?

Here is a brief overview of some of the major mechanic changes (with links to Bulbapedia in the header of each section):

Special / Physical Split:
Raven Dreamer already covered this very well in his answer, but basically, instead of the type of the move distinguishing whether it's a special or physical attack, it's now based on the attack itself. (For example, Fire Punch is now a physical move, as punching is a physical action).

Breeding:
Since Generation II, you can breed two Pokémon to obtain a Pokémon egg, which will hatch into a Pokémon. To breed them, you must put a female and a male (or any gender and Ditto) in the Day Care, and leave them. However, these Pokémon must belong to the same Egg Group in order for anything to happen. The Pokémon that hatches from the egg will be the female Pokémon you put in the Day Care, or the Pokémon that isn't Ditto. The male Pokémon is in charge of passing down attacks to the offspring. They can pass down any move that the offspring would be able to learn by level-up, TM, and certain Egg Moves (attacks that can't normally be learned by the offspring by either former method, but are programmed in as Egg Moves). Now, there are a gigantic amount of other mechanics behind breeding (ie. how the game determines what IVs to pass on, what nature to pass on, etc.), but you should probably just read the Bulbapedia article linked.

New Types:
DisgruntledGoat touched on this in his answer , but I'll mention it shortly here. Generation II introduced the Dark and Steel types. Dark types were created to counter the overpowered Psychic types, and the Steel type was introduced as a defensive typing (the only type resistant to Dragon, as Generation II added Dragon attacks other than Dragon Rage). Magnemite and Magneton became Electric / Steel from Electric (the only type change between generations).

New Attacks:
I suppose this is a bit of a given, but there are many attacks that have been added to the Pokémon series. In addition, Game Freak occasionally changes the properties of certain moves between generations, generally to balance the game. For example, the attack High Jump Kick has had many changes since it was made. It was a 85 base power move in Generation I, II, and III. In Generation I, the user takes 1 HP damage if the attack misses. In Generation II or III, the user takes half the damage it would have done if the attack misses. The damage of High Jump Kick was increased from 85 to 100 in Generation IV, and again from 100 to 130 in Generation V. However, in Generation V the PP of it was reduced from 20 to 10 and the recoil damage from missing is half of the user's health.

Natures:
Speaking of Natures, Generation III introduced natures, which basically modify a Pokémon's stat. There are 5 neutral natures, and 20 natures which increase one stat by 10% and decrease another by 10% (one nature for each possibly). For example, if I took two Pikachu with the exact same IV spread: one Bashful (neutral nature) and one Lonely (+Attack, -Defense), and trained them the exact same way (to ensure the EVs were the same), the Lonely one would have 10% more Attack and 10% less Defense than the Bashful one. In addition, Nature also determines what flavours of Pokéblock / Poffin a Pokémon likes / dislikes.

IVs (Individual Values):
This particular change doesn't really concern casual Pokémon players (heck, most people probably don't even know what IVs are), but instead of IVs being able to be 0 - 15 (as they were in Generation I and II), they can now be anywhere from 0 - 31 (Generation III and on).

EVs (Effort Values):
Yet another mechanic that is invisible to the player but exists. Generation I had an EV system (at that time known as Stat Experience) where defeating a Pokemon gave the EVs of it's base stats, and the difference between a level 100 trained Pokemon's stats and a level 100 untrained Pokemon's stats was (√Stat Experience) / 4. Since Generation III, each Pokemon has an EV value assigned to it (Zubat has 1 speed EV), and defeating the Pokemon gave that amount of EVs. While the maximum gain per stat has remained the same (up to 63 points higher on a fully trained Pokémon), the total number of EV points a single Pokémon has been capped to 127 total EVs in Generation III and on. More information in the article.

Hold Items:
In Generation I games, you could use items but not let your Pokémon hold them. However, since Generation II, you can now let your Pokémon hold items. The effects from these items could be anywhere from healing your Pokémon if they get low on health to raising the power of certain moves.

Abilities: Abilities were introduced in Generation III. Each Pokémon species has one or two abilities programmed in (and occasionally a third Dream World ability in the case of Generation V). Abilities can have effects in battle (such as Intimidate which lowers the opponents Attack upon switching in) and sometimes outside of battle (Compoundeyes raises the chance of a wild Pokémon holding an item by 50%).

Double Battles and Triple Battles: Generation III added Double Battles, where you send out two Pokémon and the opponent does the same. When you attack, you get to chose which Pokémon to target, and some moves will target multiple Pokémon (for example, Rock Side hits both of your opponent's Pokémon). Generation V added Triple Battles, which is similar to Double Battle except for the obvious difference that each trainer uses three Pokémon. The left Pokémon cannot attack the opponent's Pokémon on the right side, and vice versa.

Time of Day System:
Generation II introduced a time of day system, adding another level of realism to the game. Certain events are only triggered at certain times of day - for example, wild Hoothoot only appear at night and certain police officers in-game will only challenge you at night.

Day of the Week System
In addition to the day and night system, Generation II also added a day of week system, where certain events are only triggered on certain days (for example, you can only enter the Bug Catching contest in HeartGold and SoulSilver on Tuesdays, Thursdays and Saturdays).

Seasons:
Generation V (yet to be released outside of Japan) built on the last two systems yet again, and added in a season system. The entire overworld changes it's appearance at different seasons, and certain areas become inaccessible / accessible at certain times of the year. Each season lasts one month, so all the seasons will appear 3 times a real year. Spring occurs in January, May, and September, Summer in February, June, and October, Autumn in March, July, and November, and Winter in April, August, and December.

Pokémon Contest / Pokémon Super Contest / Pokéathalon / Pokémon Musical
Since Generation III, there have been various events that you could partake in if you wanted to take a break from battling. Ruby and Sapphire introduced the Pokémon Contest: a two-stage event where your Pokémon is first judged on various characteristics (beauty, cuteness, coolness, smartness, or toughness) that can be improved by feeding them Pokéblocks - an item created from blended berries. The second stage consists of your Pokémon using it's attacks to impress the judges (different attacks have different appeal levels and secondary effects).

Diamond and Pearl improved on this with the Pokémon Super Contest, a three-stage competition where you dress up your Pokémon, have them dance, and then impress the judges with their attacks. Instead of using Pokéblocks to increase their characteristics, you bake Poffin, a bun-like food.

HeartGold and SoulSilver has something completely different known as the Pokéathalon. Your Pokémon compete in a series of three mini-games, controlled via the touch screen. Depending on how well you do, you gain points, and these points can be spent on items to help you outside of the Pokéathalon. Instead of the characteristics that the contests use, 5 Pokéathalon stats were introduced - Speed, Power, Skill, Stamina, and Jump. Unlike the contest characteristics, the Pokéathalon stats are pre-determined by the species of the Pokémon.

Black and White added the Pokémon Musical. The first stage is similar to the first stage of the Super Contest, where you dress up your Pokémon. Your Pokémon then perform in the musical, and if the audience likes their performance (determined by how your Pokémon are dressed), they will throw items that you can keep.

Here are a few more changes not mentioned yet:

New Dark and Steel types which weren't around in Generation I. Dark was mainly added to counter the incredible power that Psychic pokemon had in the first gen - they were fairly strong pokemon and their only weakness - Bug - had no remotely powerful moves. Steel is an excellent defensive type - it has a couple of weaknesses and neutrals but the majority of types are not very effective against it.

A few other type-advantage changes were made - for example Psychic was immune to Ghost-type moves in Gen I, from Gen II Ghost is super-effective against Psychic. I think Poison changed one of its strengths/weaknesses. Here is the current type chart for reference.

From Gen II, pokemon now have Genders - male, female or genderless. This affects breeding as Kevin describes above, as well as a couple of abilities and moves like Attract. Another minor addition was 'prevolutions' - e.g. Pichu is a baby pokemon that initially could only be obtained by breeding.

Many new types of evolution, including Happiness (itself a new mechanic), trading with hold items, time of day and some quite obscure methods. There's a neat one in the upcoming Black/White games, where you have to trade two specific pokemon and they kinda 'merge' parts into each other - just like The Fly!

Many pokemon now have multiple forms (or 'formes' as it's sometimes written). For example in Gen IV there is a new pokemon Burmy, the female of which evolves into Wormadam. However, depending on what terrain you're on when it evolves, it becomes a different form. Each form has different stats and learns different moves.

The most important changes would be concerning the Physical / Special attack split. If the last game you played was Yellow, you may remember that Fire, Water, Electric, etc. attacks used the pokemon's SPECIAL stat, while Fighting, Rock, Ground, Normal, etc. attacks used ATTACK.

This is the reason Hitmonchan was a bad pokemon in the 1st generation games -- it learned Fire, Thunder, and Ice punch, but lacked a high SPECIAL* stat to effectively increase the power of those attacks.

*As of Generation II, SPECIAL has branched off into SPECIAL ATTACK and SPECIAL DEFENSE.

However, as of generation IV (of which Platinum is a part of) the individual attacks are either PHYSICAL or SPECIAL -- the aforementioned Fire Punch is a PHYSICAL Fire attack, while Flamethrower is a SPECIAL Fire attack. Generally, most pokemon have a preference for one or the other depending on whether their ATTACK or SPECIAL ATTACK stat is higher.

For the more in depth information you're interested in, I would direct you to Serebii.net. Between their main site and help forums (or even their chatrooms) you should be able too find whatever further clarifications you might need.

As to the starter pokemon you mentioned, they seem to be available as a reward in HeartGold and SoulSilver, but do not appear in Platinum / Pearl / Diamond.