I followed this document on storing relative paths:
Relative Paths in ArcGIS
But when I move the ArcMap document (along with my data in the same folder), the layers do not show up and there is a red exclamation points on the side of the layers. When I open the properties of the map document that I just moved, the "Store relative pathnames to data sources" is already checked.