Following the steps below will make your permalinks look like: www.mydomain.com/videos(Category)/the-video(Post)
Visit the Settings > Permalinks page of your WordPress administration dashboard.
Select the Custom Structure option, and enter this value:
/%category%/%postname%/
Click Save Changes
There currently is no way (that I know of) to include the taxonomy in the permalink. One way around this is to instead assign subcategories, which will be incuded in the permalink.
eg: www.mydomain.com/videos(Category)/funny(Subcategory)/the-video(Post)
You can convert your existing taxonomies into top-level categories by visiting the Tools > Import page, and using the Categories and Tags Converter.
You can then convert the top-level categories into subcategories on the Posts > Categories page.