Early Arcade Beginnings
Collectibles started appearing in games as early as the arcade games from the 1980's. One of the earliest examples is Pac-Man, where the entire game consists of collecting dots. From there, many other arcade games of the era started to add in collectibles like this. Most would serve no other purpose than to simply give you extra points, however, the entire goal of video games from that era was to get as high a score as you could on the leaderboard. Some games later on introduced collectibles that would give you an extra life, which was useful for gaining more and more points.
Donkey Kong was released in the arcades in 1981, and it introduced a new style of gameplay which would come to be known as Platforming. It brought over the idea of collectibles into this new style of game, with points awarded as Mario collects items such as hats, parasols, and purses. Pitfall! was released on the Atari 2600 in 1982, and introduced gold as the main objective for Pitfall Harry to collect.
This was expanded upon when Super Mario Bros. was released for the NES in 1985. Now instead of simply collecting a big stack of gold bricks, you instead go around and collect a bunch of gold coins. If you collected 100 gold coins, you would get an extra life. Mario did this method of collectibles in games so well that many platformers released after it copied this method, and many today still do.
The Second Evolution, Collectibles in 3D Games
While collecting stuff in 2D mainly consisted of gathering a bunch of the same object in a level, 3D games started to have a different approach to it. The early 3D platforming games on the PS1 and the N64 still had you go around collecting coins or rings, but many of them now also had something else to collect. Some 2D games in the 16-bit era also did this, most notably the Sonic games, where you could collect crystals for a reward at the end of the game.
The earliest example of this would probably be Super Mario 64, instead of simply collecting coins, you were now also collecting Power Stars. Collecting stars would unlock new levels for you to play and allow you to finish the game, however in order to keep the player from becoming stuck anywhere, the programmers added in more stars than necessary to every level so you wouldn't need to collect every star in a given level in order to progress. Because of that, the Mario series added 3 new games for the players to collect stars: Super Mario 64 DS, Super Mario Galaxy, and Super Mario Galaxy 2.
Completionists and Useless Collectibles
The advent of extra stars in Super Mario 64 led to people having the urge to complete the game to it's fullest by collecting each and every star, and making sure there was nothing they forgot to collect. These people became known as "Completionists".
Developers quickly became aware of completionists and their urge to collect everything and anything just to complete a game 100%. In response to this, they started putting in a vast number of collectibles in their games.
Very quickly, developers begin to introduce useless collectibles in their games. That is, collectibles that you would simply collect for the sake of collecting. A perfect example of this is the flags found in Assassin's Creed. There are hundreds of flags scattered throughout the game's large area, and there is no impact on gameplay whatsoever for finding them; the only benefit to gathering all of them is the unlocking of several Achievements.
However, some developers found ways to actually make the collectibles meaningful; for example, the Hidden Packages in Grand Theft Auto III. Every time the player found 10 of them, an item would be unlocked at their save points, ranging from handguns to bulletproof vests, flamethrowers and rocket launchers. This was continued in Grand Theft Auto: Vice City, and in Grand Theft Auto: San Andreas, the three major cities each contained their own unique collectibles, each with their own set of rewards.
Unfortunately, developer Rockstar seems to have lost their way. Grand Theft Auto IV's collectibles were 200 pigeons scattered throughout Liberty City, which must be shot and murdered to be "collected". In addition to getting the player in trouble with the law for firing a weapon in public, there was only an Achievement when all were found. Adding insult to injury, more birds, seagulls this time, were added in the DLC The Lost and The Damned. Likely due to the extremely negative response to GTA IV's pigeons, Rockstar's latest open-world game, Red Dead Redemption, features no such collectibles at all.
Eventually, games began to have multiple types of useless collectibles and some even began to track which ones you've collected on a stats screen. Open world games adopted this the most, however, many action games adopted them as well.
Many games nowadays have some form of collectibles in them, weather it be Cog Tags in Gears of War, Stars (again) in Super Mario Galaxy, or gold in N, as long as we keep collecting them, collectibles are here to stay.