I saw 仕方 in a sentence regarding how to pray at a shrine and 方法 when asking for different way to get a destination. Can they be used interchangeably?

[s0apgun]

Can they be used interchangeably? Yes and no. It really depends on what you're trying to convey.

仕方 is generally used to modify another noun in the form Xの仕方 to mean the way of X. This meaning has some kind of inferred natural meaning associated with the noun its modifying which will be picked up from mainly the verb.

方法 is used by itself to mean method or system and takes on a similar meaning to 仕方 by modifying a verb in the form ～する方法 to mean how to do something or a method of doing.

You can modify a noun with Xの方法 to mean the method of X which is loosely similar.

料理の仕方 the way of cooking (often directly followed by a verb)
料理の方法 cooking method
料理をする方法 method of doing cooking

Another option is やり方。

Great explanation, thank you. I hadn't seen it used much in my material so wasn't too sure, but this makes sense!

I'm not a native, but I have the feeling that 仕方 is used more often when discussing aesthetics, that is, the fashion in which you do something, whereas 方法 is used to discuss which method (of the many viable alternatives) you use to accomplish a goal.

That's a fair point. I'll keep that in mind until I come across something that says otherwise..

When in doubt, that lesser-known king of the dinosaurs, Thesaurus Rex, can be of assistance.

Translation of the important bits! I'd recommend reading the whole thing, though!
This includes 手段.

仕方→ The actions you take to accomplish something.
手段→ The actual thing you use to accomplish something. (Means of transportation = bus, train, plane, etc.) Or anyway a more concrete means.
方法→ Both meanings. When used for the same meaning as 仕方 it represents more of a logical or thought-out method than simply a way to do something.