What follows is an overview of some of the sources that I've used during my research into my ancestry both before and after arrival in Canada. The majority of sources mentioned are available online mostly because it’s a lot easier than searching through texts manually and because they are all available without needing to visit the various archive buildings around Canada (Edmonton and Ottawa mostly) and Europe (Vienna, Lviv, Kyiv, Ternopil, Chernivtsi, etc).
My family came from the regions of Galicia and Bukovina in modern Ukraine and settled in Alberta in the region centered on the Star settlement east of Edmonton, thus the sources I describe are generally centered around those regions. Likely there are similar resources for settlements in Saskatchewan and Manitoba.
Family Tree Software
I’m sure there are many programs available for organizing a family tree both online and offline. The program that I chose when I started is Legacy which is free with a paid upgrade available (which I haven’t seen a need for yet). I think most programs can exchange data using a common .ged file format.
For mobile access to my family tree I’ve been using the program Shrubs on my iPhone. There may be other programs out there which are better and there will likely be equivalent programs for other mobile platforms such as Blackberry and Android but I haven’t had reason to look.
Passenger Lists
The passenger lists for ships arriving in Canada between 1865 and 1922 have been filmed and put online by the government archives: Passenger Lists, 1865-1922. This is useful if you know exactly what ship your ancestors came to Canada on but not very useful for searching. Fortunately the records have all been transcribed by volunteers and are searchable on Ancestry.ca. As with any transcription of handwritten records the accuracy will vary considerably (not that the original records are necessarily spelled correctly anyway - the immigration officials would usually write something that sounded roughly the same as the name the person gave).
Searching on the Ancestry.ca website is free but viewing the records requires a subscription which starts at $10 per month. The Calgary Public Library has a site license so you can use the full Ancestry.ca site from computers at the library. Edmonton likely has a similar license. The other option is to take advantage of the advanced search options to narrow down the results until you have the ship pinned down.
For example, I already knew that George Alexandruk came to Canada around 1902. If you don’t even have an approximate date or names of family members the census records can help narrow it down. For example the 1911 Census asked for when a person immigrated. So I would go the Ancestry.ca, select the Passenger Lists page and search for George Alexandruk with an arrival date of 1902. This returns 175 records. Because I’m reasonable confident that the date is close to right I would then modify the search to require the date to exactly match 1902 +/- 1 year. This reduces the list to 10 names, 5 of which look like possible matches. The best match is a George Alexandriak who arrived in Montreal, Quebec. This isn't nearly enough information to locate a ship from so the next step would be to make the search more precise. First I would change the name to require an exact match on “Alexandriak” and remove the first name so that any family members would show up in the search. This reveals what looks like a family of four: George, Loria, Kasterera and Iwan. Next I would remove the +/- 1 year condition from the search and require an exact match on 1902. This returns no results so I know the family must have arrived in 1901 or 1903. I would try searching for each of those in turn. In this case the show up in 1903. Next I would try adding a month to the search, cycling through the months until the family shows up. In this case it’s in July 1903. Doing the same thing with the day reveals that they arrived on July 2, 1903. Going to the Canadian archives page and searching for ships with a date of arrival of 1903/07/02 shows two ships, one arriving in Halifax and one in Montreal/Quebec. Thus I would know that this family came on the Lake Champlain and I could look through the images on the passenger list website until I found the family. In this case they appear on page 3 of 17 where I can see the ages of each person and can compare against the census records or whatever I already know.
Of course, it’s possible that the name is spelled so poorly that it doesn't show up in searches in which case I’d start entering variations of the surname and using the first name that is least likely to be misrecorded (so Maria, Anna, George and Joseph are more likely to be accurate than Kazimir, Penteley, Varvara, etc.). It can be quite a slow process but it’s a lot easier than searching the lists for every ship hoping to find a match.
Ancestry.ca also has the passenger lists for ships which departed from Hamburg which can also be worth searching as it’s possible that the spelling might be more useful. I don’t know of anyplace other than the Ancestry website where those records can be viewed so if you don’t have a subscription you likely won’t be able to view them. I've found that about half of my relatives came through Hamburg while the others were Liverpool or Antwerp, neither of which seems to have departure records available.
Homestead Applications
The homestead application forms filled out by settlers in Alberta are available on microfilm at the Provincial Archives in Edmonton. These forms will include information like when the homestead was settled, how much land was cleared and farmed each year, what improvements had been made and what livestock the family had. To find the file number for a homestead use the search at http://abgensoc.ca/homestead/search.php?_mode=advanced. Searching by location is easier than searching by name as the names are often spelled in interesting ways. If the record is old enough you might be able to find it online in the U of A collection: Alberta Homestead Records. They are very slowly copying the films and putting them online, but if the film doesn't start with “20” or “21” they won’t have them. The Provincial Archives of Alberta (8555 Roper Road, Edmonton) has microfilms of all these applications that you can view for free. They do charge 35 cents per page to print copies.
Often included in the file with the application form will be other documents relating to the homestead such as previous applicants on the land who abandoned the claim and in some cases copies of the naturalization document of the claimant. In the case of one of my ancestors there were actually three previous claims made which had been abandoned for various reasons (mostly that the land wasn't very good).
Census Records
In Canada the census records are made public after 92 years. This means that currently the most recent one released is the 1916 Census of the Prairie Provinces. The 1921 national census should be available in 2013. The census records are all sorted by location so it is very helpful to know what section the person lived on. As the Ukrainian immigration didn't really start until the late 1890s the ones to look at will be the 1901 and 1911 national census and the 1906 and 1916 prairie censuses (special censuses were added in the north-west for those years due to the fast growing population). The information collected changes each year but will include names, ages, birth place, citizenship, language and ability to read & write. In 1901 there was a second form which recorded the buildings on the land. 1906 recorded livestock counts.
All of the census records released so far have been indexed so it is possible to search on Ancestry.ca to locate records before looking up the actual file from the government archives website. For example searching the 1916 census for the name “Meronek” turns up a result for Sam Meronek in Kindersley, Saskatchewan which I wouldn't have know to look at otherwise.
Censuses - Library and Archives Canada
Homestead Photos
The University of Calgary has some aerial photos of Alberta online dating from 1950. http://contentdm.ucalgary.ca/collections/airphotos2/www/mapsheet.php?ms=83H
Of course, unless you can find some landmark nearby it can be very difficult to identify what homestead is which. I had some luck using the modern satellite map view on Google Maps to pick out forests and lakes that were still around. To find a homestead on Google Maps you can convert the Dominion Land Survey (township/range) coordinates to latitude and longitude using the http://www.baseloc.com/dls/ website.
Aerial photos showing just the homestead buildings are also available. I believe these can be ordered from http://www.homesteadaerial.com/request.html
Cemeteries
Many of the tombstones from Alberta cemeteries have been photographed and transcribed at: Prairie Souls: Cemetery images/transcriptions The photos are often linked to people who were thought to be relatives along with some information not found on the tombstone itself, though in my experience this information is unreliable.
Land Grants
The Library and Archives Canada collection also includes the actual land grants giving the settler title to their homestead once their application was approved. They can be searched at http://www.collectionscanada.gc.ca/databases/western-land-grants/001007-100.01-e.php
Some of the results will include an image of the document but most just give the microfilm where it is located. You can get copies of these from the archive or the films can probably be borrowed through your local library. There isn't a lot of useful information on these documents other than the date of the grant.
Newspaper Archives
Google has scanned many newspapers which can be searched at http://news.google.com/newspapers. Obviously the usefulness of this will vary considerably depending on the names you are looking for. Meronyk is rare enough that most of the results are relevant. Alexandruk is harder to search for. Mielimaka is rarely spelled the same way twice so it’s difficult to get useful results.
Books
Covered on the Reference Books page.
Maps
For a general map of the Galicia/Bukovina region highlighting places that the majority of immigrants in Alberta came from: http://tapor.ualberta.ca/heritagevillage/placenames/bukgal.php#top
An 1882 map of Galicia: http://feefhs.org/maplibrary/austro-hungary/ah-galic.html
A 1:200,000 scale military survey of Austria done around 1910 (look for Csernyivci to find the Bukovina region): http://lazarus.elte.hu/hun/digkonyv/topo/3felmeres.htm
A 1:75,000 scale map started around 1894 is available online from the New York Public Library. The legend for these maps is online: http://semanchuk.com/gen/maps/spezialkartor/legend.png. More informations about this and the previous set of maps can be found at: http://semanchuk.com/gen/maps/index.html#spezialkarte
A 1:100,000 scale topographic map done by the Soviet Union around 1942 is available online. It looks like this is a Polish website that mirrored material that the University of California, Berkeley used to have online - which is probably why that university only has the index on their website now.
Gazetteers
A directory of cities/towns in Ukraine is available at: http://www.fallingrain.com/world/UP/ This can be somewhat useful as it often lists the same village with a variety of spellings and gives the latitude/longitude for each village.
There is a gazetteer with information about many villages from the Austrian empire circa 1907 online. The Galicia volume and the Bukovina volume are of particular interest. An excellent guide on how to use these is http://www.halgal.com/gemeindelexikon.html. There is a ton of useful information in these including the population of each village, the religions, languages, houses, livestock, churches and land types along with what parish the church belonged to. The place names are typically German or Polish.
There is another comprehensive gazetteer which I've seen references to: the Genealogical Gazetteer of Galicia by Brian Lenius which is described at http://www.halgal.com/ggglenius.html and can be ordered from http://www.lenius.ca/GazetteerOrder/GazetteerOrderForm.htm. The Calgary library doesn't have a copy of this book, but it might be available from other libraries.
Family History Center
The Mormon church has by far the most extensive collection of genealogical records in the world. This includes copies of the parish records from many villages in Ukraine which include births, marriages and deaths often as far back as 1800. They have set up Family History Centers in many cities where you can view these microfilms. To find a convenient location, check: http://www.familysearch.org/eng/Library/FHC/frameset_fhc.asp. Be sure to check the hours each one is open to find one that is not only conveniently located but is also open when you can go there.
To determine what microfilms are relevant for you there is a location search. If you can’t find what you are looking for you can try searching for “Ukraine”, then selecting that and then “View Related Places” which gives a list of provinces within Ukraine. Select the relevant one “Chernivtsi” for example and then “View Related Places” to get a list of districts, repeat the process and it will list the villages. Click the “Church records” link, then “metrical books”, and “Film notes”. For each set of records for the village there will be a Film Number and Item Number. The film number identifies the microfilm and the item number is the position within the microfilm as each film usually contains records from several villages.
Note that each metrical book existed in two copies. The original was kept in the village and each year the records were transcribed into a separate copy kept in another location. This is why there is sometimes multiple overlapping records for a village and why some are marked as “original”.
Once you know what film you want to view you can order it for viewing at your local Family History Center: https://www.familysearch.org/films/ Note that a short term loan gives you 90 days to view the film (minus all of the days that the center isn't open) and costs $6. Depending on the film it might arrive in days or weeks.
Once the film has arrived the volunteers at the Family History Center should be able to help you set up the microfilm readers to view the records. The center I use also has the ability to save digital copies of pages once you've found an interesting record. I would guess that is the same at other locations but I can’t say for sure.
The parish records themselves are more or less readable depending on how good the priests handwriting was and what language was being used. The Catholic church generally used Latin so the alphabet is the same as English but the first names of the people are a Latin equivalent (so “Joannes” instead of Ivan, “Gregorius” instead of Hrihorii, etc.). The Orthodox church on the other hand would often use Cyrillic which might be Ukrainian, Russian or Romanian depending on the time period and region. Note that Romanian was in the middle of switching it’s alphabet away from Cyrillic in the 19th century so the records often combine letters from each alphabet in the same word during this period. Watch out for ‘ω’ which is equivalent to ‘o’, ‘θ’ which is equivalent to ‘th’ and other letters that I haven’t figured out yet.
Other Links/Sources
The following are other links that I've bookmarked over the years. Some might be useful, many are likely dead, but I haven’t really had time to dig through them.
http://www.halgal.com/vitalrecords.html
http://www.rootsweb.ancestry.com/~ukrwgw/index2.htm
http://www.ourfutureourpast.ca/home.htm (Alberta Heritage Digitization Project)
http://www.torugg.org/TUGG%20Links/tugg_links.html#locate
http://www.feefhs.org/links/galicia.html
http://www.feefhs.org/links/bukovina.html
http://www.rootsweb.ancestry.com/~ukrgs/resources.html
http://www.brama.com/index.html
http://sumno.com/gallery/chernivetskyj-skansen/?page=3 (photo gallery of what appears to be Bukovinian equivalent to the Ukrainian Cultural Heritage Village)