Maybe this link will help: http://pares.mcu.es/
Many Spanish archives have been digitalized by the government of Spain and are on the web. Here you may be able to see passenger records of emmigrants to America. Perhaps you can find your grandparents there.
Catherine is "Catalina" in Spanish.
Good luck with your search.