Before heading here, have you done all the searches that you can on available online censuses,etc...Speaking from experience, there was a Red River Descendant's reunion to which people came from all over the world, and they wished they'd had more time for the local archives....Also if you have Hudson's Bay Co. history, that section alone could easily eat up 5 days of searching....
In the archives you can look for, but no guarantess there are records for your ancestors surviving... land records, wills, censuses, (including early 1800's Red River Settlement, heads household & head counts only ) ship's records, all of which can be scanned to disc...You can look at Maps, images from earlier towns/areas/ photos if they were prominent citizens...and more
http://www.gov.mb.ca/chc/archives/ The library jacquie has mentioned is attached to the archives, so is no extra travelling. In there you can peruse old newspapers.... first by searching on a database available and then you can look for the actual page on microfilm & scan for your records...They also have the henderson directories on microfilm... You may find tons of information or very little, it's always a crap shoot. But you may want to contact them to see if they have any advice prior to you coming....
There are many hotels downtown within walking distance... you can use google maps help with proximity, directions, etc. I may even be able to help you a little if I am around at the time you visit...you can p.m. me
