How do we know that the cosmic background radiation comes from the early universe? How do we know that the source of the CMB comes from the early universe, and we don't simply observe the rare interstellar or intergalactic dust of 3K temperature?
 A: The Big Bang model is the current standard model for the evolution of the universe. It is built up by using General Relativity equations and particle data and astrophysical observations. It is a successful model because there has been no unexplainable contradiction, i.e. the model developed to encompass and explain mathematically, what looked like contradictions.
That the universe is not in a steady (thermodynamic) state  is an observational fact, it is expanding and recently accelerated expansion has been observed with better measurements.
The Cosmic Microwave Background is electromagnetic radiation, i.e. photons of very low frequency, not dust. There are experiments measuring and mapping the sky for this .


Graph of cosmic microwave background spectrum measured by the FIRAS instrument on the COBE, the most precisely measured black body spectrum in nature.[8] The error bars are too small to be seen even in an enlarged image, and it is impossible to distinguish the observed data from the theoretical curve.

The current history of the universe goes as follows:

In the Big Bang model for the formation of the universe, Inflationary Cosmology predicts that after about 10^−37 seconds the nascent universe underwent exponential growth that smoothed out nearly all inhomogeneities. The remaining inhomogeneities were caused by quantum fluctuations in the inflaton field that caused the inflation event. After 10^−6 seconds, the early universe was made up of a hot, interacting plasma of photons, electrons, and baryons. As the universe expanded, adiabatic cooling caused the energy density of the plasma to decrease until it became favorable for electrons to combine with protons, forming hydrogen atoms. This recombination event happened when the temperature was around 3000 K or when the universe was approximately 379,000 years old. At this point, the photons no longer interacted with the now electrically neutral atoms and began to travel freely through space, resulting in the decoupling of matter and radiation.

The color temperature of the ensemble of decoupled photons has continued to diminish ever since; now down to 2.7260±0.0013 K, it will continue to drop as the universe expands. 
The extreme uniformity of the map of the sky , 


The detailed, all-sky picture of the infant universe created from nine years of WMAP data. The image reveals 13.77 billion year old temperature fluctuations (shown as color differences) that correspond to the seeds that grew to become the galaxies. The signal from the our Galaxy was subtracted using the multi-frequency data. This image shows a temperature range of ± 200 microKelvin.

Note that the color map is about  5 orders of magnitude smaller than the current black body temperature of the CMB, the all-sky is extremely uniform. It was the measurement of this uniformity that forced modeling the beginning of the universe quantum mechanically, as at the time the photons decoupled the universe could not come into thermodynamic equilibrium: due to the light cones of special relativity there were parts not possible to thermodynamically interact with other parts so as to homogenize the  radiation.
We know it is radiation, we know it is uniform and has a black body spectrum, and it fits in the whole current model of the universe. Dust certainly does not.
A: Because is relative homogeneous and isotropic(it has different density variations in all directions) and therefore the photons have undergone gravitational redshift.Also, photons lifetime is of the order of lifetime the universe.
A: Theory I:  There is CMB corresponding to ~3 K blackbody radiation coming at us from all directions.
Theory II:  There is ~3 K blackbody radiation coming to us from "rare" interstellar dust and there is no CMB.
Testable difference:  There would be directions where the intensity of the radiation (photons per m^2 per steradian per second) were different.  We would expect greater  intensity in the plane of the galaxy (with much pollution from other light sources and attenuating objects) than perpendicular to the plane of the galaxy.  There would be additional bright beacons in the direction of other galaxies.  In fact, we should expect the low temperature dust beacons from other  galaxies to vary in frequency (temperature) due to variations in energy density and, generally, to be hotter the farther away (further back in time, more compact) they are.
Result of observation:  We do not observe this directional difference in  background radiation intensity.  In fact, we observe the opposite: greater intensity out of the plane of the galaxy and much scatter and loss for photons trying to traverse the plane of the galaxy.  Further, we find that in the direction of other galaxies, the CMB is no more intense and does not seem to vary in temperature.
A: The short answer is we know that cosmic background radiation came from the early universe because it is the farthest out light we can see. And just based on chronological order and the speed of light we know what came first. It wouldn't matter what theory of the universe you believe in, we can see that background radiation came earlier than all the other light. 
There are a few methods they use to measure these distances. For up close things they use trigonometry and parallax techniques. Farther out they use standard candle readings of type 1-A nova which emit a certain a unique signature . For the really far stuff they use red shift and expansion comparisons. 
