Embedded boundary methods for CFD (Computational Fluid Dynamics) simplify a number of issues. These range from meshing the fluid domain, to designing and implementing Eulerian-based algorithms for fluid-structure applications featuring large structural motions and/or deformations. Unfortunately, embedded boundary methods also complicate other issues such as the treatment of the wall boundary conditions in general, and fluid-structure transmission conditions in particular. This paper focuses on this aspect of the problem in the context of compressible flows, the finite volume method for the fluid, and the finite element method for the structure. First, it presents a numerical method for treating simultaneously the fluid pressure and velocity conditions on static and dynamic embedded interfaces. This method is based on the exact solution of local, one-dimensional, fluid-structure Riemann problems. Next, it describes two consistent and conservative approaches for computing the flow-induced loads on rigid and flexible embedded structures. The first approach reconstructs the interfaces within the CFD solver. The second one represents them as zero level sets, and works instead with surrogate fluid/structure interfaces. For example, the surrogate interfaces obtained simply by joining contiguous segments of the boundary surfaces of the fluid control volumes that are the closest to the zero level sets are explored in this work. All numerical algorithms presented in this paper are applicable with any embedding CFD mesh, whether it is structured or unstructured. Their performance is illustrated by their application to the solution of three-dimensional fluid-structure interaction problems associated with the fields of aeronautics and underwater implosion.