Khovanov homology can be computed quite well, by Dror Bar-Natan's algorithm, as Ben says. It's nowhere near as good as algorithms for computing the Jones polynomial however.
The basic idea is that the speed of the computation depends largely on the "girth" of the link diagram. This is greatest number of intersections you see with a horizontal line. Within each girth, the algorithm applies to be a small degree polynomial in the number of crossings. However changing the girth dramatically affects the algorithm. Girth 14 is critical -- we can do up to about 80 crossings. See my paper with Freedman, Gompf and Walker on the smooth 4-d Poincare conjecture for details. Girth 12 and below is 'easy', and yes, 100 crossings is plausible, but more likely in weeks than seconds! Girth 16 and above seems to be out of range of current computers.
It's important to point out that memory constraints are the real issue for large Khovanov homology calculations. There's only a limited degree to which you can parallelize the computation, and so you end up wanting a single big computer with tonnes of RAM. The latest implementation of Dror's algorithm (my partial rewrite of Jeremy Green's program) tries to cache a lot of stuff of disk, but nevertheless we've done runs on 32gb machines and wished we had more memory!
As Ben says, Khovanov-Rozansky is much harder, and the purely combinatorial calculations you do for Khovanov homology get replaced by lots of commutative algebra. Ben at one point had a program that was doing this -- I'm not sure what the status of that is.
Knot Floer homology is a different matter. Even though there is now a nice 'cube of resolutions' picture for Knot Floer homology, it's only directly for knots, rather than tangles, so Dror's divide and conquer strategy doesn't apply. Dylan Thurston and others have a local description for tangles, but I don't know that anyone has tried implementing it. Computers aren't yet good at A_\infty tensor products!
If anyone is ever interested in writing better programs for Khovanov homology (or indeed trying to generalize to cover some of the other cases), please contact me, as I have some ideas! I'm no longer interested in writing code myself, but I'm happy to talk about it and assist. Particularly next semester at MSRI, if anyone is interested in doing some link homology programming they should talk to me.
Check out these lecture notes (and the references listed therein) http://www.renyi.hu/~cast2012/ng-cast.pdf
1) Visualize elements of $ST^{*}\mathbb{R}^{3}$ as unit length vectors -- not necessarily based at the origin -- in $\mathbb{R}^{3}$. The projection $\pi$ onto $\mathbb{R}^{3}$ send each vector to its basepoint. The unit conormal bundle bundle $\Lambda_{K}$ consists of those vectors orthogonal to $K$. If you apply the time-$\epsilon$ Reeb flow (=geodesic flow) to $\Lambda_{K}$ for $0<\epsilon$ very small and then apply $\pi$, you will get the boundary of a tubular neighborhood of $K$ in $\mathbb{R}^{3}$.
2) I take it that this question means ``Why can't you define homology groups by counting Reeb chords and holomorphic disks (which are easier to work with than DGAs)?'' You can only define homology groups by counting holomorphic strips (disks with 2 boundary punctures) if you can say that the only way that strips break (in a Gromov limit) is into a pair of strips. This if often possible for Lagrangian intersection problems by imposing various geometric constraints which rule out undesireable degenerations of homolorphic disks. In this Legendrian case, this does not work if you are to obtain a Legendrian isotopy class invariant. Play around with some examples of Legendrian knots as in Etnyre-Ng-Sullivan's paper and this will become clear.
3) Not really: (Mild) You have to first identify $ST^{*} \mathbb{R}^{3}$ with the 1-jet space $ J^{1}S^{2}=\mathbb{R}\times T^{*}S^{2}$ of $S^{2}$. This isn't too hard to intuit (the zero section of the 1-jet space is identified with $\pi^{-1}$ of the origin in $\mathbb{R}^{3}$). (Medium) Now think about what the conormal bundle $\Lambda_{\mu}$ of the unknot $\mu$ looks like in this 1-jet space. As an approximation, the projection of this torus onto $S^{2}$ is obtained by applying the geodesic flow to a fiber of the unit tangent bundle of $S^{2}$ for time $t\in[0,2\pi]$. (Spicy) If $K$ is braided about $\mu$, then $\Lambda_{K}$ will be braided about $\Lambda_{\mu}$ in $J^{1}S^{2}$. It's well-known that any knot is braided about the unknot. (Habanero) Use a direct limit argument and Ekholm's Morse flow trees technique to read off the holomorphic disks from the braiding data.
4) They're both defined by looking at the representations of the DGAs.
5) Ng's papers describe how knot contact homology encodes various knot polynomials. It is conjectured that you can use it to obtain the HOMFLY-PT polynomial. As for knot homology theories, I'm sure that people have thoughts on this but as far as I'm aware no conjectures have been anounced.
Best Answer
I can say something about this for Heegaard Floer homology. Given a 3-manifold Y, you can take a Heegaard splitting, i.e. a decomposition of Y into two genus g handlebodies joined along their boundary. This can be represented by drawing g disjoint curves a1,...,ag and g disjoint curves b1,...,bg on a surface S of genus g; then you attach 1-handles along the ai and 2-handles along the bi, and fill in what's left of the boundary with 0-handles and 3-handles to get Y.
The products Ta=a1x...xag and Tb=b1x...xbg are Lagrangian tori in the symmetric product Symg(S), which has a complex structure induced from S, and applying typical constructions from Lagrangian Floer homology gives you a chain complex CF(Y) whose generators are points in the intersection of these tori and whose differential counts certain holomorphic disks in Symg(S). Miraculously, its homology HF(Y) turns out to be independent of every choice you made along the way. We can also pick a basepoint z in the surface S and identify a hypersurface {z}xSymg-1(S) in Symg(S), and we can count the number nz(u) of times these disks cross that hypersurface: if we only count disks where nz(u)=0, for example, we get the hat version of HF, and otherwise we get more complicated versions.
Given two points z and w on the surface S of any Heegaard splitting we can construct a knot in Y: draw one curve in S-{ai} and another in S-{bi} connecting z and w, and push these slightly into the corresponding handlebodies. In fact, for any knot K in Y there is a Heegaard splitting such that we can construct K in this fashion. But now this extra basepoint w gives a filtration on CF(Y); in the simplest form, if we only count holomorphic disks u with nz(u)=nw(u)=0 we get the invariant $\widehat{HFK}(Y,K)$, and otherwise we get other versions. The fact that this comes from a filtration also gives us a spectral sequence HFK(Y,K) => HF(Y).
This was constructed independently by Ozsvath-Szabo and Rasmussen, and it satisfies several interesting properties. Just to name a few:
For knots in S3 it is also known how to compute HFK(K) combinatorially: see papers by Manolescu-Ozsvath-Sarkar and Manolescu-Ozsvath-Szabo-Thurston.
The relation to other knot homology theories isn't all that well understood, but there are some results comparing it to Khovanov homology. For example, given a knot K in S3:
Anyway, that was long enough that I've probably made several mistakes above and still not been anywhere near rigorous. There's a nice overview that's now several years old (and thus probably missing some of the things I said above) on Zoltan Szabo's website, http://www.math.princeton.edu/~szabo/clay.pdf, if you want more details.