Will impose a caliper help to reduce the bias or reduce the variance? On the lecture notes provided by my tutor, the caliper matching is introduced under the methods of nearest neighbour matching. Basically, on the slide, it says the nearest neighbour matching lacks common support restriction, as all units matched to their nearest neighbour no matter how far away. But this potential bias can be improved if we impose a caliper. Hence, I think by imposing a caliper, the bias should be reduced at the cost of increasing variance. (For there might be a decrease in a number of observations.)
However, in Dehejia and Wahba (2002), the caliper matching becomes the opposite: by imposing a caliper, a larger comparison group will be selected and hence reducing the variance at the cost of increasing bias. 
In fact, trying to reproduce the result from the paper, I run the code
set seed 12345
generate x=uniform()
sort x
psmatch2 train age agesq educ educ2 married nodegree unem75 unem74 unem74hisp re74 re75 re74_2 re75_2 black hisp, ///
    cali(0.0001) outcome(re78) logit ties
pstest

on my stata, and the outcome suggests that the on support treated group dropped from 185 to 27. If I am still using the one-to-one with replacement nest neighbour matching, the observations of my controlled group should not have more than 27 observations, if I understand the concept of common support and matching correctly. However, on the paper, the number of observation for a caliper of 0.0001 is actually 337 out of 2507. 
I have no idea why such a difference could be possible.
 A: I think that your intuition regarding the concepts of common support and matching is correct. I also fully agree with your instructor about the warnings issues about NN matching.
Having said that, I think we need to fully appreciate what "with replacement" entails. Let's consider what will happen in the case of two sample that do not have substantial common support: When matching with replacement a lot of instances from the treatment group can be matched to the same instance from the control group. That is because the same control instance can be the nearest neighbour for many treatment instances.
As the NSW sample and the PSID sample have a small overlap regarding their pre-treatment characteristics this translates into not having a lot of unique control samples picked.
To that extent, yes, if we are using 1-to-1 matching with replacement we cannot ever have more control samples picked than the number of treatment samples. Imposing a caliper can increase the total number of control units matched to a treatment case; this will lower the expected variance of the treatment effect estimate but can potentially increase the bias because we are more likely to make an unsuitable match. 
One the other hand, with caliper matching we will use all  of the control  units  within a  pre-defined propensity score radius (the caliper). In that sense, a larger sample size is not unexpected. Note that caliper matching is far from a silver-bullet. Some treatment units may not receive any matches because there are no neighbours within the given caliper. As Morgan & Winship, propose in Chapt. 5 in Counterfactuals and Causal Inference you might be better to "use a hybrid approach, where in a second step all treatment cases without any caliper-based matches are then matched to a single nearest neighbor outside of the caliper."
I do not have access to Stata, but assuming you can use R's MatchIt package, you can compare the output of:
out1 <- matchit(treat ~ re74 + re75 + educ + black + hispan + age, 
                 data = lalonde, method = "nearest", replace = TRUE)
out2 <- matchit(treat ~ re74 + re75 + educ + black + hispan + age, 
                 data = lalonde, method = "nearest", replace = FALSE)

In out1 we use 1-NN matching with replacement and then out2 1-NN matching without replacement. The matched dataset created by out2 is smaller than out1 exactly because a number of control subjects are reused. (The data lalonde is a subsample from the NSW study.)
In general, be skeptical towards procedures that remove data aggressively.
Finally, you are right to question the actual numbers reported in the paper. I think the wording leaves something to be desired. By 56 the authors most probably denote the number of matched control units, rather than "No. of observations" which itself is unambiguiduous if it refers to the whole matched sample or just the treatment sample of it.
Unfortunately I cannot replicate exactly because I do not have the full dataset; the unemployment figures are provided by the authors. I can replicate the analysis without these figures in which case they are 66 (not 56) matched control units against 185 treatment units. So 56, while quite low is not totally improbable. I attach the R code used below:
rm(list=ls())
NSW = read.table('http://www.nber.org/~rdehejia/data/nswre74_treated.txt')
PSID = read.table('http://www.nber.org/~rdehejia/data/psid_controls.txt')

names(NSW) = c('treatment', 'age','education', 'black', 'hispanic',
               'married', 'nodegree', 're74', 're75', 're78')
names(PSID) = names(NSW)

allData = rbind(NSW, PSID)

library(MatchIt)
Q = matchit(treatment ~ age + education + I(age^2) + I(education^2) +
                        black + hispanic + married + nodegree + 
                        re74 + re75 + I(re74^2) + I(re75^2),
            data = allData, method = "nearest", 
            distance = "logit", replace = TRUE )
Q

