The recent possible discovery of Planet Nine by Batygin & Brown (2016) has caused quite a stir, in the astronomy community, Astronomy Stack Exchange, and the rest of the world. This is, of course, in part because any mention of such a discovery will cause a stir, but it is also in part because of the claimed probability if the movements of the Trans-Neptunian Objects (TNOs) being purely by chance: 0.007%, or 1 in 14,000, which corresponds to a probability of ~ 3.8$\sigma$.
That said, the actual probability that this planet exists is a bit lower - 90%, according to Brown, and 68.3%, according to Greg Laughlin, an astronomy at UC-Santa Cruz who knew of the results prior to the paper's publication. The difference between these odds and the odds mentioned in the paper is due to the fact that perhaps there are other contributing factors that could have caused the movements of the TNOs - and also that these informal numbers are more like guesses than estimates.
The answers to Why hasn't the "9th Planet" been detected already? have already given a variety of methods that won't work in the case of Planet Nine, and why they haven't worked. Besides the obvious possibility that Planet Nine just doesn't exist, here are some of them:
- It might be confused with a background star, blending in with the Milky Way.
- It's far away, and dim - perhaps a 22nd magnitude object., 
- Most methods of detecting exoplanets won't work, including
- Radial velocity.
- Gravitational microlensing
- Direct imaging.
- Prior surveys either don't look enough in-depth, in-depth but in other areas of the sky, or cover wavelengths in which this planet doesn't show up in. This is another problem with the use of WISE detailed in MBR's answer here. Others problems are that planet is probably not massive enough for WISE to see it, and is extremely far away. It may also be cold and have a low albedo, making direct detection hard.
I bring all this up because, surprisingly, the case of Planet Nine is very relevant to the detection of these other planets that you mentioned in your question.
HD 106906 b
There are several similarities here between this planet and Planet Nine.
- HD 106906 b has an orbit with a semi-major axis of at least 650 AU. By comparison, Planet Nine is thought to have a semi-major axis of about 700 AU, according to the estimates in the paper. That said, other orbital properties are unknown for HD 106906 b and may differ.
- HD 106906 b has a mass of about 11 Earth masses; Planet Nine has a mass of about 10 Earth masses.
One difference is that HD 106906 b may have formed where it is at the moment. Scattering, like Planet Nine experienced, appears to be unlikely. This means that the two could have different compositions - although I would think that both might be ice giants or the remains thereof, given where they formed.
In short, HD 106906 b may be very similar to Planet Nine, and while we do not know much about either property, it seems safe to say that detection methods and problems would be similar.
Fomalhaut b is a bit different. Its semi-major axis is ~177 AU - much smaller than these other two planets - and may be anywhere from 10 Earth masses to several hundred Earth masses.
Interestingly enough, Fomalhaut b was also indirectly detected, just like Planet Nine. A gap was found in Fomalhaut's dust disk, which could only have been caused by a massive planet. Later, it was directly imaged.
Direct detection might be possible if Fomalhaut b was in the Solar System, especially given its greater size and mass. Additionally, it would have an enormous impact on TNOs. However, it would be a gas giant, not an ice giant, so it would be difficult to explain how it moved out so far.
I discussed those planets to take a slight detour and talk about what might (and might not) be beyond Neptune. I'll be more explicit here.
What could be beyond Neptune
An ice giant, like Planet Nine, or the remains of one. This would have been formed closer in, near Jupiter and Saturn, which existed in a period resonance with Saturn. Other giant planet resonances would have also existed. Then a instability broke the resonances, bringing the ice giant inwards towards Saturn and then Jupiter, where it was flung outwards. This changed the orbits of the other four gas giants. I talked about this is another answer of mine, which I seem to be continuously referencing.
That said, the initial answer was incorrect, which I have since noted, and was revised. Batygin's estimates found that Planet Nine would have been ejected many, many, millions of years before the resonances were supposedly broken (according to evidence from the Late Heavy Bombardment). However, this does not mean that there could not have been a sixth giant. The simulations Nesvorný & Morbidelli (2012) that explored the evolution of a Solar System with four, five, and six giant planets found some good results with five and six giant planets.
- A super-Earth or mini-Neptune.1 These are planets that are, at the most, 10 Earth masses. Super-Earths would be terrestrial planets with thick atmospheres; mini-Neptunes would be gas planets. Note that these names do not say anything else about their compositions - for example, super-Earths are not necessarily habitable.
- Something else. The region has not yet been explored well, and there could be some other unforeseen objects. This kind of object would likely be cold, as WISE (see next section) might have detected it otherwise.
What cannot be beyond Neptune
So, assuming that there is something beyond Neptune, how can we fine it? Well, now that its existence has been hypothesized and we know where it should be, astronomers can turn telescopes towards that location and use direct imaging.
There's been some excitement because the Subaru Telescope will be used. Other optical (and possibly infrared and other wavelengths) telescopes will most likely be used as well. Answers to What wavelength to best detect the "9th planet"? (especially Rob Jeffries' answer) indicate that optical and infrared/near-infrared wavelengths will be the best choice. As of today (1/24/2016), we can only speculate on what other instruments will be used, and what their chances are of finding this planet - if it exists.
Who knows? Maybe something else unexpected will turn up.
1 Now we get into the different things Planet Nine could be. My answer to What type of planetary-mass object would Planet Nine be? covers this, but there are better answers to Ninth planet - what else could it be? than mine.
2 Be careful of the difference between an ice giant and a gas giant.