The terms Ruthenia and Ruthenians are quite complex to understand.  The confusion comes from the fact that different authors in different times have used the terms to mean very different things. 

These terms Ruthenia and Ruthenians are often used during the times of the Austrian Empire (and in modern writings about the Austrian Empire) to mean Ukraine and Ukrainians found in the empire (in its province of Galicia, what is today western Ukraine).  How could a similar people be called by two different names: Ruthenians and Ukrainians?  The answer is a historical one and as we know, history is often written by the victors of wars and geopolitics.  Thus, these terms (and even a history of Ukraine itself) come to us by way of foreign interpretation, namely Polish, Austrian and Russian interpretations.

You'll often see the terms Ruthenia and Ruthenians to mean what we now know as Ukraine and Ukrainians in popular genealogical resources such as Naturalization Papers, Immigration records, Passenger Lists, and Census returns.  Thus, a basic understanding of history is in order to understand these various terms.

In the Middle Ages, there was a large East Slavic princedom called Rus or Kyivan Rus (Kievan Rus) <Kiev is Russian, Kyiv is Ukrainian> on the territory of what is today Ukraine.  In the 14th Century, Poland took control of the western principality of  Halich.  Over a period of time, another East Slavic principality to the north, called Muscovy, grew to dominate the region including the central and eastern principalities of Kyivan Rus.  Later, Muscovy adopted the name Russia taking advantage of the great legacy of the powerful and influential Kyivan Rus.

Thus, the Ukrainian people were split between Poland and Russia.  The term Ruthenian (coming from a Latin translation of Rus) was used for the western Ukrainian people.  Russia, however, did not want to equate Ukrainians to the former great principalities of Rus, so settled on the term Ukrainian, which means "on the borderland".  <It should be noted that Russia only formally accepted Ukrainians as a unique and separate ethnic group in the early 20th Century.  Up to this that time they were often called derogatorily "Little Russians".>

There was a conscious effort on the part of Poland, then subsequently the Austrian Empire, to keep the Ruthenians from acknowledging their common ties with the millions of Ukrainians living across the border in the Russian Empire.  The Austrian Empire, being a multi-national empire, often played the Poles and Ruthenians against each other to keep both in check thus maintaining its own control in the region.

To make matters more confusing, there is yet another meaning.  The term Ruthenians is also used for a group of people living in the Carpathian mountains.  These East Slavic peoples are also referred to as Rusyns or Carpatho-Rusyns.  You'll also see terms like Lemko, Hutsul and Boyko.  This group of people were dominated by the Hungarians, who were especially cruel to their non-Magyar subjects.  For more reading on this ethnic group, visit these popular websites:

Slovak and Carpatho-Rusyn Genealogy Research Pages
Carpatho-Rusyn Society

So, if your ancestors come from the immediate region of the Carpathian Mountains, the term Ruthenian would mean Rusyn or Carpatho-Rusyn.  If your ancestors come from what is today Ukraine but not in a mountainous region, the term Ruthenian would mean the same as Ukrainian.

As a final note I must add the following (which I sincerely hope doesn't create too much confusion).  Please keep in mind that there are some that believe that Rusyns (aka Carpatho-Rusyns, aka Boyko, aka Lemko, aka Hutsul) are simply a regional variation of Ukrainians.  The scholarly debate continues between the two camps (one states that Rusyns are a unique and separate ethnic group, the other states that Rusyns are essentially Ukrainian but who were cut off from Ukraine proper by mountains and politics thus creating unique regional traits.)

The over-simplification above is meant to teach you about the terminology and is not intended to be a complete history.  For more information on this subject, you should read the following:

Kann, Robert A.  A History of the Habsburg Empire 1526-1918.  University of California Press.  Berkeley, 1974.
Kann, Robert A.  The Multinational Empire: Nationalism and National Reform in the Habsburg Monarchy 1848-1918.  Octagon Books.  New York, 1964.
Magocsi, Paul Robert.  A History of Ukraine.  University of Washington Press.  Seattle, 1996.
Markovits, Andrei S. and Sysyn, Frank E. (editors).  Nationbuilding and the Politics of Nationalism: Essays on Austrian Galicia.  Harvard University Press.  Cambridge, 1982.
Potichnyj, Peter J. (editor).  Poland and Ukraine: Past and Present.  Canadian Institute of Ukrainian Studies.  Edmonton, 1980.
Subtelny, Orest.  Ukraine: A History.  University of Toronto Press. Toronto, 1988.