Where do I start learning how to create a video game?

Gamestar Mechanic is a great place to start. Look them up and they have several exercises which will familiarize yourself with the topics for good game creation.

If you want to make games, a good free game engine (like Unity) is an easy way to start, even if you don't have any experience in programming.
There are a lot of good tutorials available (e.g. http://unity3d.com/learn/tutorials/modules/beginner/live-training-archive/coding-for-the-absolute-beginner) which try to learn you everything while actually doing it at the same time.

What's better than learning how to make a game than actually doing it? I did not have any programming or coding experience before I started studying Computer Science at university, so it's never too late to start learning it!

Luckily, there are loads of free resources online for learning how to program, specifically in games!

One of my favorite programming languages for learning is Javascript, because it's already set up to run on everyone's computer (in their browser), and you don't need to buy any programs to write in it.

I really like the JavaScript course here: https://www.khanacademy.org/computing/computer-programming/programming
For a quicker introduction to JavaScript, you can try codecademy: http://www.codecademy.com/tracks/javascript

A lot of making a game is in the planning phase.

Speaking from more of an art, UX and user interface standpoint, we spend a lot of time planning the screen flow, look, feel and mechanics of the game.

Once you have a solid concept, find a platform that will allow you to make a basic prototype to test the concept. Some great suggestions in other answers, although the 'best' platform for you will depend on the time you have and sort of game you want to make.

Construct2

CLONING an existing game using a free game engine is one of the best learning exercises -- you'll work through all the nuts and bolts of putting together a finished playable product, without getting bogged down trying to "find the fun" or needing to be able to build technology from scratch.

Pick a simple classic like Pong, Space Invaders, Combat, Missile Command, Frogger, Pac Man, etc. Even some modern games can fit the bill, like Geometry Wars or Angry Birds. (Something that doesn't require a lot of complex art to be fun.)

If you are completely new to game development or don't want to program, you can get fantastic results (relatively) quickly using GameMaker.

If you know how to program already, Unity or Unreal are fine choices.

If you are an experienced developer in another field who wants to jump head-first into making games, pick an engine and consider skimming Jason Gregory's "Game Engine Architecture" for an overview of all the major tech pieces that go into any game/engine.

Then get to work!

All of these tools have extensive tutorials and excellent support forums. Use them as needed, always working towards the features that your clone game needs. Pretty soon, you'll have something playable. And soon after, a finished game. At that point, you'll have enough experience to decide what the next step is for you.

I'd recommend looking at something like GameMaker or Scratch which are both free tools to get the basic understanding of coding. If you're ready to get more advanced then YouTube is your friend, I'd recommend Brackey's YouTube channel for Unity tutorials. I'm not a coder and use these tools to teach a weekly kid's coding club!

I've used Clickteam Fusion and it's forebears for many years, but these days I wouldn't actually recommend it. It's good for making quick prototypes, but not much else. Unity and Unreal 4 are both free and easy to get started in.