Learn Hardcore Russian: В автошколе мне стоит дышать глубже, чтобы не нервничать. - At driving school it’s worth breathing deeper so as not to be nervous.

In мне стоит дышать..., the pattern is (кому?) стоит + infinitive = it is worth / advisable for someone to do something.
So мне (dative) marks the person for whom the advice applies: “for me / I should…”.
The actual action (дышать) is still done by the same person (me), but Russian often expresses this with a dative “experiencer” rather than a nominative subject.

What does стоит mean here? Is it the same as стоить “to cost” or стоять “to stand”?

Here стоит comes from стоить and means it’s worth it / it makes sense / it’s advisable.
It does not mean “cost” in this sentence, and it’s not from стоять (“to stand”).
Common use: (кому) стоит + infinitive = “someone should / it would be good to…”

Could I replace мне стоит with мне нужно or мне надо? What’s the difference?

Yes, but the nuance changes:

мне стоит дышать глубже = it would be a good idea / advisable (softer, recommendation)
мне нужно / мне надо дышать глубже = I need to / I must (stronger necessity)
мне следует дышать глубже = I ought to (more formal)