For some, DNR garmin (http://www.dnr.state.mn.us/mis/gis/tools/arcview/extensions/DNRGarmin/DNRGarmin.html) may be enough for converting shapefiles to gpx files but this program may not always work - especially for large files. I have found it easiest to convert ArcGIS shapefiles to KML and then to GPX files.
Shapefile to KML
Depending on the content of your shapefile, there are two different options for creating a KML.
1) Open-source Shp2kml, available at: http://www.zonums.com/shp2kml.html . This would be my first choice. The GUI is very straightforward and gives you quite a few options for customizing your KML, such as: the color scheme, roll-over effect, and which attributes are displayed. NOTE: The list of acceptable Datums is kind of short. Found it easiest to just re-project shapefiles to WGS84. Also, found that this tool would not always work for shapefiles with especially long text attributes and/or multi-part polygons. (This is discussed in more detail in a past blog called Shapefile to Google Earth kml - Customize Symbol Properties and Labeling (NO PROGRAMMING REQUIRED!).
2) Create a layer file of your shapefile and use the ‘Layer to KML’ tool in ArcGIS. You have less authority over the output with this method. Limited customization of color scheme can be done in Google Earth (unless you would like to program some fancy customizations). NOTE: Actually saves the file as a KMZ; resave the KMZ as a KML for conversion to GPX in GoogleEarth. If you are using this options, delete all of the attribute fields that you do not want to show up in Google Earth – this information pops up when the feature is clicked.
KML to GPX
Lots of options.
1) Open-source KML2GPX, available at: http://groups.google.com/group/kml-support-getting-started/msg/ec5e2ae637ed4bfc
3) Open-source GPSbabel, available at: http://www.gpsbabel.org/
4) Built-in tool on gpsies.com, available at: http://www.gpsies.com/convert.do
I know that DNR garmin and the tool on gpsies.com are not good for very large datasets.