Yes, FXO should work.
Q. What type of gateway interfaces are supported with this feature?
A. The IP Communications Voice/Fax network modules (NM-HD-1V, NM-HD-2V, NM-HD-2VE), the IP Communications High-Density Digital Voice/Fax network modules (NM-HDV2, NM-HDV2-1T1/E1, NM-HDV2-2T1/E1), the Digital T1/E1 Packet Voice/Fax Network Module (NM-HDV and all bundle variations), the High-Density Analog and Digital Extension Module (EVM-HD) and the Packet Voice/Fax Digital Signal Processing Module (PVDM2) are supported. These interfaces support analog and TDM gateway ports, including FXS, FXO, T1, E1, fax etc.
http://www.cisco.com/en/US/products/ps5854/products_qanda_item0900aecd8016c49f.shtml
A very good configuration guide:
http://www.cisco.com/en/US/products/sw/iosswrel/ps5207/products_feature_guide09186a0080357589.html#wp1043334
