Victorian sensibilities did draw distinct lines between the genders. However, they aren't necessarily the same lines we draw today. As such, do not limit yourself to your own gender's department. Sometimes it is easier to find what you are looking for in the department of the other gender. This most often applies to thrift store shopping, but can sometimes apply to other places as well.
Frilly shirts are generally found in the women's section. I've been informed that even frilly men's shirts generally end up in thrift stores in the women's section.
While no-nonsense jackets can be found in abundance in the men's section, more decorative styles such as velour jackets will generally be found in the women's section.
Striped pants, which were popular in Victorian times, are more commonly found in the women's section, particularly if you're looking for a narrow leg, which was also popular in Victorian times.
Leather coats and jackets can easily be found in both men and women's sections without having an obvious gender-specific look to them. Belts are also often divided by gender, but can frequently be used interchangeably. If you're going to use a belt as a strap and need something longer than a belt, definitely look to the men's section, where belts are always longer.
If you're wanting a more solid, practical look to your costume, look to the men's section. Cargo pants and work boots are two items that specifically come to mind.
Purses are obviously a woman's accessory, but if you're looking for material to create other items such as straps and pouches, purses are a great place to start.
If a woman is attempting to create a more manly character (such as an engineer or a pilot who prefers pants to skirts), feel free to look in both sections. While women have plenty of dress shirts available to them, for example, they do have a distinctly different look than a man's dress shirt. Don't limit your options.