From WoWWiki

Bonuses for Strength can only be obtained through Red gems, Orange gems and Purple gems.

Color	Name	Effect(s)
Red	[Bold Tourmaline]	+4 Strength
	[Bold Blood Garnet] || +6 Strength
	[Bold Living Ruby]	+8 Strength
	[Don Amancio's Heart]	+8 Strength
	[Don Rodrigo's Heart]	+8 Strength
	[Bold Crimson Spinel]	+10 Strength
Orange	[Inscribed Flame Spessarite]	+3 Strength	+3 Crit Rating
	[Inscribed Noble Topaz]	+4 Strength	+4 Crit Rating
	[Inscribed Pyrestone]	+5 Strength	+5 Crit Rating
	[Etched Fire Opal]	+5 Strength	+4 Hit Rating
	[Champion's Fire Opal]	+5 Strength	+4 Defense Rating
	[Resplendent Fire Opal]	+5 Strength	+4 Resilience Rating
Purple	[Sovereign Shadow Draenite]	+3 Strength	+4 Stamina
	[Sovereign Nightseye]	+4 Strength	+6 Stamina
	[Sovereign Tanzanite]	+5 Strength	+6 Stamina
	[Sovereign Shadowsong Amethyst]	+5 Strength	+7 Stamina