The word "try" here is meant as a "trial."  Men's souls and their wills were being tested during the American Revolution.  For most of the war, the American colonists were not winning.  In the North, the British army occupied cities such as New York.  The Continental Army was on the run, suffering one defeat after another.  Goods such as food grew scarce as many of the farmers were fighting in the war.  The war in the South and West was growing desperate as pro-British and pro-colonial guerrillas fought.  It looked like the British would win the war, and the colonial leaders would be hung.  Paine wrote this line in order to convince the patriots to stay the course and continue fighting.  He wrote this to encourage civilian support for independence as well as to encourage soldiers to stay in the field even though their cause looked lost.  

When Paine uses the word “try” in this context in “The Crisis,” he means something like “test.”  In other words, he is saying that the times they were living in were the times that tested men’s souls.  He is saying that their situation was going to test men (and presumably women as well, though people did not think they were important in those days) and see what they were made of.

We can see this meaning by looking at the next sentence at the beginning of this first pamphlet of Paine’s.  He goes on to say that

The summer soldier and the sunshine patriot will, in this crisis, shrink from the service of their country; but he that stands by it now, deserves the love and thanks of man and woman.

Paine is saying that some people will not stand up for their country and their freedom.  These are the people who, in today’s language, were “jumping on the bandwagon” of freedom when times were good.  They are “fair weather friends” of their country.

Paine is saying that these times are going to test people out.  The times are going to see who is really a true patriot and who is not.  The former deserve our thanks and love while the latter deserve to be scorned.  By saying “these are the times that try men’s souls,” Paine is saying that these are the circumstances where we find out who fits in each of these two categories.

What does Paine mean when he says in The Crisis that "these are the times that try men's souls?"

When Paine says this, he means that the time he was in (the second winter of the Revolutionary War) was a very difficult time.  In this context, to "try" means to "test."  Paine is saying that these difficult times will test people's souls, determining who is a true patriot and who is not.  Paine says that this test will determine which people only support the cause when it seems to be winning (these are the "summer soldier and the sunshine patriot") and which truly have the moral fiber to back the revolution even when things are going badly.

Paine saw that the revolution was in a crisis and he was trying to encourage more people to stand up and support it so it would not collapse.