I have noticed a lot of people use of instead of have, for example: "that must of been really annoying". Is this correct?
In speech, this is merely a relaxation of pronunciation - should have becomes should've, must have becomes must've. This relaxed pronunciation is fine.
However, the contracted have (i.e. -ve) should not be written as of. Of sounds similar to -ve, so many people erroneously think should of and must of is how to write should've and must've. Should of and must of are improper.
Use should have and must have when you are writing, unless you are writing dialogue, or writing informally. In those cases you also have the option of using the contractions should've and must've:
That must have been really annoying.
Or, in dialogue and informal settings (e.g. chat):
"That must've been really annoying!" said Jack.