There are 300 side missions to complete, 16 of which are missable.
Chapter 2
1-2-1: Challenge from Security
Unlock this by speaking to the Shinra captain in LOVELESS Avenue. He will challenge you and you will gain access to this mission line.
Completing all 6 missions and speaking to him again will reward you with Craftsman Monthly, which is needed for all wagon types.
8-2-1: SPR Mako Stone
In the Shinra building on the SOLDIER level, speak to the scientist in the Materia Room to unlock this mission line.
Completing all 6 missions and speaking to him again will reward you with six materia and the achievement Master Mako Stone Miner.
Chapter 3
2-1-1: Beginnings
In Sector 8-Fountain, speak to the man on top of some stairs to unlock this mission.
2-1-2: Approaching the Outskirts
In Sector 8-LOVELESS Avenue speak to the employee walking about to unlock this mission.
7-1-1: Freight Recall
In the Shinra building, on SOLDIER level speak to a 3rd class SOLDIER in the Briefing Room to unlock this mission line.
Completing all 6 missions and speaking to him again will reward you with Premium Tires, which are needed for all wagon types.
Chapter 4
2-1-3: Sightings in Sector 5
After you get your wallet back from Bruno, speak to a girl in Sector 5-Slums to unlock this mission.
2-1-4: Defend the Slums
Unlocked by speaking to another girl standing right outside the wall leading to the Slums Park.
(thanks to LW N1ghtm4r3)
Chapter 5
2-1-5: Highway Closed
Speak to the Shinra infantry troop in the Shinra Building entrance upstairs floor to unlock this mission.
2-1-6: Truth in the Wasteland
Speak to the scientist in the Shinra Building Exhibit Room to unlock this mission line, after completing Missions 2-1-1 through 2-1-5.
Completing all 5 missions and speaking to him again will reward you with Mythril Tools, which are needed for all wagon types.
6-2-1: Slum Development Plan 1
In the Shinra Building entrance, speak to the man talking with a woman to unlock this mission line.
4-3 Mission Line: The Crescent Unit
4-3-1: Defeat the Scout Units
4-3-2: Obliterate Advance Elements
4-3-3: Foes in the Wutai Base
4-3-4: Mobile Units
4-3-5: The Enemy's Stronghold
4-3-6: Stop the Assailants
In Sector 8-LOVELESS Avenue speak to a 2nd Class SOLDIER about catching Wutai Spies.
For every spy you discover, you unlock a mission.
You don't need to complete the missions but you have to catch the spies in order.
Refer to the Wutai's Nemesis guide for their locations:
If by Chapter 7 you haven't unlocked these and you've reached Nibelheim, don't bother with this achievement on this playthrough, as mission progress DOES NOT carry over to NG+.
If you've unlocked these then you can continue to unlock this achievement because the rest of these missions are unlocked either by story progression or non-missable side mission progression.
For Mission Lines M10-1 and M10-2, they need to be unlocked but they are not missable.
M10-1: Cactoid Secrets is unlocked by finding and defeating the Kactuar in M3-1-3: Eliminate the Copies.
M10-2: Tonberry Quests is unlocked by finding and defeating the Tonberry in M6-1-5: Buried in the Caverns.
Both enemies are visible, meaning they are not a random encounter and in both instances you have to finish the mission itself afterwards.
Now, for the mission list:
M1: Shinra Electric Power Company (30)
M1-1: Training Missions (6)
M1-2: Peacekeeping Troops (6)
M1-3: Weapons Development (6)
M1-4: Plan for New Equipment (6)
M1-5: Special Ops Weapons Laboratory (6)
M2: Monster Research Project (30)
M2-1: Monsters in Midgar (6)
M2-2: Monster Reports (6)
M2-3: Monster Incidents (6)
M2-4: Unexplored Territorries (6)
M2-5: In Search of the Unknown (6)
M3: Genesis' Forces (30)
M3-1: Enemy on the March (6)
M3-2: Major Offensives (6)
M3-3: Clash with Genesis' Forces (6)
M3-4: Genesis Evolution (6)
M3-5: The Strongest Copies (6)
M4: To End the War with Wutai (30)
M4-1: Pursue the Remnants (6)
M4-2: Behind the Scenes (6)
M4-3: The Crescent Unit (6)
M4-4: The Remnants Strike Again (6)
M4-5: Annihilate the Crescent Unit (6)
M5: Hojo's Laboratory (24)
M5-1: Sample Monsters Lv. 1 (6)
M5-2: Sample Monsters Lv. 2 (6)
M5-3: Sample Monsters Lv. 3 (6)
M5-4: Sample Monsters Lv. 4 (6)
M6: Seeking Precious Items (36)
M6-1: Looking for Items (6)
M6-2: Midgar City Development (6)
M6-3: Zack, the Treasure Hunter (6)
M6-4: Zack, the Clean-Up Guy (6)
M6-5: Zack, the Corporation Crusher (6)
M6-6: Counter-Mafia Project (6)
M7: Seeking Priceless Items (36)
M7-1: Recall Missions (6)
M7-2: Precious Things (6)
M7-3: ESP Development Project (6)
M7-4: Contacts from P (6)
M7-5: Orphans Escaping (6)
M7-6: The Accessory Craftsman (6)
M8: Zack, the Materia Hunter (36)
M8-1: Starting Out (6)
M8-2: Mako Stones (6)
M8-3: To Hell and Back (6)
M8-4: From a Hot Treasure Hunter (6)
M8-5: Anonymous Hints (6)
M8-6: Yuffie's Notices (6)
M9: Great Cavern of Wonders (36)
M9-1: Invitation to the Underground (6)
M9-2: Stirrings (6)
M9-3: In Search of What? (6)
M9-4: Realm of Demons (6)
M9-5: Unknown Energy (6)
M9-6: Doors to the Unknown (6) [incl. Minerva]
M10: Mysteries of the World(12)
M10-1: Cactoid Secrets (3)
M10-2: Tonberry Quests (3)
M10-3: Fun in the Sun! (3)
M10-4: More Fun in the Sun! (3)
Missions get progressively harder but the one golden piece of advice I can give you is to always hug the walls. It is possible to avoid almost all enemy encounters until you reach the mission target.
If you do get in a random encounter, try to escape and if you die you can just retry the battle.
About every 5% of missions completed (every 15 missions) you will get a reward.
5%: Thunder Blade MAG+1
10%: Titanium Bangle
15%: ATK Mako Stone x30
20%: Dark Blizzara MAG+1
25%: Crystal Bracelet
30%: Rush Assault ATK+1
35%: Magic Stone x30
40%: Firaga (M) MAG+1
45%: Precious Watch
50%: Wall (M) SPR+10
55%: Goblin Punch (M) ATK+1
60%: Graviga (M) HP+100%
65%: Fat Chocobo Feather x30
70%: Moogle Power VIT+60
75%: Assault Target
80%: Full Cure (M) HP+200%
90%: Force of Nature
100%: Heike Soul