As mentioned the problem of cylinder box intersection reduces to the problem of line-parallelogram intersection, and line segment-cylinder intersection.
I will assume that you know how to intersect a line and a parallelogram. Here is a sketch for solving the line segment-cylinder intersection:
The canonical equation of an elliptic cylinder aligned with the $Z$ axis and having center $(c_x, c_y, c_z)$ is given as:
$$\frac{(x-c_x)^2}{a^2} + \frac{(y-c_y)^2}{b^2} = 1$$
The parametric form of a ray is given as:
$$\vec{r}(t) = \vec{o} + t\vec{d}$$
Then by plugging r into the canonical equation one gets:
$$\frac{(o_x + td_x -c_x)^2}{a^2} + \frac{(o_y + td_y -c_y)^2}{b^2} = 1$$
Solve the quadratic equation for $t$ and you have your intersection. If the discriminant is negative then there is no intersection. To get a rotated cylinder, the easiest way is to apply the inverse rotation to the ray (the equation may be modified however too). Note that for a line segment, you simply need to check whether $t \in [t_0, t_1]$, where $\vec{a} = \vec{o} + t_0\vec{d}$ is the first point of the line segment, and $\vec{b} = \vec{o} + t_1\vec{d}$ is the second one.
EDIT: To clarify you further questions in the comments:
1) a,b in the denominator are the radii along the $X$ and $Y$ axes respectively. In the trivial case where $a=b=r$ we have the canonical equation for a circular cylinder:
$$(x-c_x)^2 + (y-c_y)^2 = r^2$$
2) For the intersection between the cylinder axis and the box a rotation is only required if your box is OOBB and you want to use your AABB intersection code.
3) The solution of the quadratic equation is trivial (note, I renamed $a,b$ to $r_1,r_2$ to further emphasize that they are the radii):
$$\frac{(o_x + td_x -c_x)^2}{r_1^2} + \frac{(o_y + td_y -c_y)^2}{r_2^2} = 1$$
$$r_2^2(o_x + td_x - c_x)^2 + r_1^2(o_y + td_y -c_y)^2 = r_1^2r_2^2$$
$$(r_2^2d_x^2+r_1^2d_y^2)t^2 - 2(r_2^2d_x(c_x-o_x) + r_1^2d_y(c_y-o_y))t + r_2^2(c_x-o_x)^2 + r_1^2(c_y-o_y)^2 - r_1^2r_2^2 = 0$$
Let us substitute:
$$A = (r_2^2d_x^2+r_1^2d_y^2)$$
$$B = (r_2^2d_x(c_x-o_x) + r_1^2d_y(c_y-o_y))$$
$$C = r_2^2(c_x-o_x)^2 + r_1^2(c_y-o_y)^2 - r_1^2r_2^2$$
Then you have the quadratic equation:
$$At^2 -2Bt + C = 0$$
$$D = B^2-AC$$
If $D<0$ there is no intersection between the ray $\vec{o}+t\vec{d}$ and the cylinder, otherwise:
$$t_1 = \frac{B-\sqrt{D}}{A}, t_2 = \frac{B+\sqrt{D}}{A},$$
give you the two intersections (it is one intersection if $D=0$).
Now let your segment vertices be $\vec{v}_a = \vec{o}+t_a\vec{d}$ and $\vec{v}_b = \vec{o} + t_b\vec{d}$. If $t_a \leq t_1 \leq t_b$ then you have an intersection at $t_1$, if $t_a \leq t_2 \leq t_b$ then you have an intersection at $t_2$, otherwise there is not intersection.
