Horseshoes are found only in Las Venturas. You will receive $100 and some luck every time you collect one, and when you collect all 50, your luck will be maxed and you'll also get $100,000. Also, four weapons will spawn in front of The Four Dragons Casino, which are M4, SMG, Combat Shotgun and Satchel Charges.
It is highly advisable that you finish the "Green Goo" mission before you start to go after these, as this will spawn a jetpack next to your safehouse at Verdant Meadows Aircraft Graveyard. This is because some Horseshoes are located on top of buildings, and having the Jetpack will make it a lot easier to acquire them.
NOTE: The Horseshoes are listed in sequential order, meaning it can be difficult to understand if you pick one at random from the listings. The starting point is the front of The Four Dragons Casino.
#1) Across the street is the Come-A-Lot sign. At the top is the horseshoe.
#2) Head back to the Four Dragons and head towards the backside. The south side has an entrance to a garage (you can't use it). On the roof of the garage is the horseshoe.
#3) Head south, across the freeway, to Rockshore West. Find the northernmost row of houses next to the freeway. The horseshoe is next to a garbage can behind the easternmost house.
#4) Don't leave this area. Among the middle row of houses is another horseshoe. From the Last Dime Hotel side, head east to the third row of houses and you should find the horseshoe in the small backyard of the southernside house.
#5) Head west to the Randolph Industrial Estate. Under the bridge leading out of town is another horseshoe.
#6) Head a bit west to the Blackfield Chapel. The horseshoe is on top of the chapel building, on the east side.
#7) Go north and inside the LVA Freight Depot. On the south side, just to the left of the checkered flag icon, is a horizontal rectangular shaped building. There are ramps heading down around this building and the horseshoe is located in the southeastern one.
#8) In the same lot is a orangish colored building. On the south side is a small gap between the warehouse and the wall and the horseshoe is there.
#9) Go west to Greenglass College and you'll find the horseshoe in the center of the four grassy areas in front of the college.
#10) Go northeast to the airport. Find the main building and the horseshoe is on the west side of it against the wall in the center.
#11) Stay in the airport and go north to where the runway is U-shaped. To the east is the horseshoe on the ground.
#12) Go near the northwest corner of the airport and you should find another horseshoe in plain sight just to the south of safehouse icon on your map.
#13) To the west of the last one is a building in Whitewood Estates that looks kind of like the receiver of a telephone. The horseshoe is in front of the building on the north side.
#14) Go north and find the large red building. To the west is a wall with barbed wire. The horseshoe is between the wall and the building.
#15) Way to the north is a highway just to the right of the train tracks. There should be a sign that says "Welcome to Fabulous Las Venturas." The horseshoe is at the bottom of it, on the ground.
#16) Find the railroad tracks just as they enter Prickle Pine on the west side. Face south and go south to the very first house and look to the right. The horseshoe is to the right of the garage in front of the door.
#17) Go northeast to find the Yellow Bell Golf Course and go to the north side of the building. On the west side is the horseshoe in a little alcove with a window.
#18) Go directly east and find the cone-shaped apartment complex with a pool in the center. The horseshoe is at the north end of the pool.
#19) Just to the east are some tennis courts. The horseshoe is located in the southern set of courts, on the east side.
#20) Go all the way to the northeast corner, where K.A.C.C. Military Fuels is located. Go through the northwest building from the west side and when you exit the east side, you'll see the horseshoe. If you have done "Up, Up and Away," you'll probably have passed it. (Going into the base with the Jetpack does not give you any stars.)
#21) Go southeast to Creek and the little mall there (3 clothing stores and 2 fast food places). Follow the sidewalk around to the east side of the strip mall to find the horseshoe.
#22) Just to the southwest is a large building with a guitar-shaped swimming pool. The horseshoe is in the swimming pool (there's an oyster under the diving board).
#23) Just to the west of the last one are train tracks. Get on the tracks and follow them under a tunnel to the south. The horseshoe is in the tunnel, just to the right of the tracks a bit into the tunnel.
#24) Go back to where you entered the tunnel and head a bit west to find a heart-shaped sign that says "Erotic Wedding Chapel." The horseshoe is on the roof of the building there.
#25) Go northwest and find the pizza place on Roca Escalanta. West of there is a church and a Discount Wedding Store with a parking lot to the west. Just west of that is a wall and the horseshoe is just on the other side.
#26) Just to the south of the last one is a car wash. The horseshoe is in between the car wash and the building to the east, at the base of a large pole.
#27) Just to the southwest of the last one is a multi-story parking garage with a helipad on the roof. There is a very tall building next to it. The horseshoe is at the top of the building (there's a parachute there too).
#28) Find the gym in Redsands East. To the east of it is a Welding & Weddings building and a souvenirs store. Go into the alleyway between those buildings and jump the wall behind the souvenirs building. You should see the horseshoe at the north end.
#29) The next horseshoe is on top of the souvenirs store.
#30) Go directly west of the gym to find a building with a large lot and a hedge going around it. The horseshoe is on top of this building.
#31) Head a bit west by southwest to find a steakhouse (there's a Bobo the Monkey billboard to the north). Just to the west is a casino. The horseshoe is on a ledge on the roof in between the two buildings.
#32) A bit northwest of the last one is a building and some large containers. Go to the northwestern set of containers and the horseshoe is on the west side of the containers closest to the street.
#33) To the southwest of the last one is a very large building with a large parking lot to the north of it. You should see a "Restaurant" sign on the building to the north and a wall to the right of it. The horseshoe is on the wall.
#34) Go back to the front of the souvenirs store just to the east of the gym. Across the street is an alleyway with a white fence-like thing in the way. Jump over it and follow this path find another horseshoe.
#35) Just south of the last one is a tattoo place and a barber. Just to the north of that is a motel. On the east side is The Strip and just north of the alleyway between the tattoo parlor and motel is a place you can climb onto. Do so, and continue past the Motel sign. Make a U-Turn past the sign and climb onto the next area. Take the left pathway when presented with two ways to go and follow it to find the horseshoe.
#36) From the last one, go directly east two blocks until you get to the casino in Old Venturas Strip where you have a safehouse. The horseshoe is right in front of the casino sign.
#37) Go south a bit to find the Cluckin' Bell. Just south of that, along The Strip, is a sign that says "Venturas Steaks Drive-Thru." The horseshoe is on top of it.
#38) Go west one block to find a 24/7. Just to the east is a parking garage. In the alleyway between the 24/7 and garage is the next horseshoe.
#39) Just to the southwest of the last one is The Visage. There is a big pond out front with waterfalls. The horseshoe is underneath the middle waterfall, on the rocks.
#40) Just to the southeast of The Visage is The Clown's Pocket hotel (you can buy a hotel suite to use as a safehouse). Get on top of the awning-roof and go a bit west to find the horseshoe.
#41) Go directly east of the last one to find a strip mall with a pizza place and a clothing store. Just above the entrance to the clothing store is a balcony. The horseshoe is on that balcony.
#42) Just to the east of that strip mall is the Julius Thruway East and you should see a billboard advertising the Victim clothing store. The horseshoe is on the east walkway next to the billboards at the top.
#43) Go back to the entrance of The Clown's Pocket and head southwest to find Pirates in Men's Pants. To the north of the entrance is a skull rock and the horseshoe is on the rocks directly in front of that skull.
#44) To the south of Caligula's Palace is the Royal Casino and to the east of that is a parking garage. Enter the south end of the garage and go up to the third level. Go all the way to the opposite end of the level and you should see the horseshoe on the west side.
#45) Just to the south of the parking garage is a pyramid. The horseshoe is at the top.
#46) There is a small ledge circling The Camel's Toe. The horseshoe is on the east side of the ledge, directly west from the church.
#47) Go southwest to find Come-A-Lot. You'll find a bunch of castle-like towers on the north end. There is one tower without anything pointing out, meaning it's flat. The horseshoe is on that tower.
#48) Two block east of the last one are some small buildings. Find the middle set of buildings and climb the first set of stairs of the east one. You should find another set of stairs and some balconies. You can find the horseshoe on the middle balcony.
#49) A couple of blocks south of the last one is a wedding chapel. The horseshoe is on the roof behind the steeple.
#50) Go east across the highway and the train tracks to find some buildings in a fenced area. Go to the southernmost building and you'll find the horseshoe on a dumpster on the south side of the building.