Is this the "correct" way of doing things or should we be instanciating the utility class as and when we need it?
From OOD point of view it depends :-)
For pure functions you should use static methods in Java/C#. In C# you can also try to use extension methods as others describe.
For utility methods which are not pure functions (for example reading some file) you should create an instance to improve testability (allow mocking for example).
The difference is that the latter, although don't keep any state directly, they communicate with some external components having own, possibly changing state. This external state may cause this utility method to return different results over time (for the same input) making it much harder to test and to reason about. It is good design principle to distinguish between pure functions and such utility methods by putting the latter as explicit instance methods.
However in Java practice "mocking argument" usually takes preceeding, since it doesn't allow to mock static methods.