The easiest way to gain skillups is to produce orange or yellow colored schematics. Orange schematics have a 100% chance of giving you a skillup, yellow has a lower chance but is still reasonable. Stay away from green unless you have an abundance of ingredients or nneed the produced components for something else, as it has the lowest chance of giving you a skillup.
Note that the yellow and green colored schematic skill-up chance is not fixed directly to its color, but instead gradually changes. This explains why a schematic that just turned green may provide skillups relatively often, whereas one that is about to turn grey will give you a skillup much more rarely.
In order to max your skill out the easiest, cheapest and fastest way, it is best to stick with the simplest schematics requiring the least ingredients possible.

Walkthrough
Increasing you skill is normally a process that slowly advances as you level up. To make it easier to decide which schematics are easiest to level up with, or if you start from scratch at a high level, this walkthrough should prove quite useful.
Do not take this chapter as a fixed set of rules if you are skilling up while levelling. Simply making whatever you have the ingredients for can work out nicely.

Take note: Gnomes have a +15 bonus to engineering. This bonus does not affect skill-up rates. Take this into account if you’re using the table below. It effectively means you only need to skill up to 360 'real'' skill to make the 375 required schematics. Seeing that the last points are the most expensive to skill up, gnomes have it easy.

0-75 Apprentice Engineering

You are making a pretty large amount of copper bolts here. These are needed to skill up in the next tier. You will need to train to journeyman Engineering at the trainer when you reach 75 skill.

75 – 150 Journeyman Engineering

Try selling the Deadly Blunderbusses you make, these are used in a quest in Ashenvale. Making these might net you a profit.

150 – 225 Expert Engineering

Make sure you keep 10 Gyrochronatoms. These are used in a quest in badlands, so it's a possibility to sell the rest in the AH.
Same goes for all the advanced target dummies, these are used in quest in Desolace. They probably won't sell too fast as few people quest in that zone. You might be better off using them up and getting some ingredients back.
The Accurate scopes should sell nicely in the AH.
Ammunition generally doesn't sell too well until you get to the post 300 skill arrow makers.

225 – 300 Artisan Engineering

Note: If you cannot get the Thorium Shells schematic at a reasonable price, the best option is to carry on making Thorium Tubes until you hit 300.
Mithril Casing is used for a quest in Un'goro Crater. You should be able to sell them.
The Spellpower Goggles can be disenchanted to net you some enchanting materials, which you can auction away.

300 – 375 Master Engineer
Note: there are two paths in this guide for 300-375. Each with different materials used. One focuses primarily on getting your final skillups (the toughest ones) by making repair bots, which use a lot of Khorium Ore. You will need to buy your Khorium and Primal Fire and later sell the repair bots to make up for the lost gold. The other path takes the more conventional approach of using primarily materials that you mine yourself and crafting Adamantite Rifles.
I'd suggest only choosing Path 1 if you have a enough gold to buy the Khorium Ore.

Note that this is a cheaper path if you just compare the materials. However, Adamantite rifles are not particularly valuable and will barely sell in the auction house, unlike the Repair bots.
You will have to decide for yourself which of the two is the best route for you to take.

Grand Material Tally For 1-375

Buying Materials: Ore Or Bars?
When buying your materials, should you buy ore or bars? The answer used to be ore because it was cheaper than bars before BC's release. Now, with the addition of a profession that uses raw ore, the prices on ore have risen. Even so, buying ore over bars is frequently still worthwhile. Compare prices on the AH to decide whats best to buy for which metal type.