A connection mark is a mark that is automatically applied to all packets of a connection. You mark the connection on one packet, and all other packets in the same connection will have the same mark. This is very useful for identifying traffic to a host as well as the return traffic.
Packet marks only are applied to one packet, and do not propagate to other packets in the same connection.
Sometimes you use the two together because it requires fewer resources to do so. Let's take the following example:
/ip firewall mangle
add protocol=tcp dst-port=80 src-address=1.1.1.0/24 out-interface=WAN chain=forward action=mark-packet new-packet-mark=test
add protocol=tcp src-port=80 dst-address=1.1.1.0/24 in-interface=WAN chain=forward action=mark-packet new-packet-mark=test
That would mark all packet that are HTTP traffic between hosts on the 1.1.1.0/24 network and web servers with the packet mark 'test'. However, for each and every single packet you would have to do a lot of work. Is this packet TCP? Yes. Is it going to destination port 80? Yes. Is the source address within 1.1.1.0/24? Yes. Is it going out the WAN interface? No. Oh. OK. Is it a TCP packet? Yes. Is it sourced from port 80? Yes. And so on. Every packet that is traffic to a webserver would require four comparisons, every packet that is traffic from a webserver would require 8 comparions, and every packet that doesn't fit either would also require 8 comparisons, plus whatever happens afterward.
/ip firewall mangle
add connection-state=new protocol=tcp dst-port=80 src-address=1.1.1.0/24 out-interface=WAN chain=forward action=mark-connection new-connection-mark=test passthrough=yes
add connection-mark=test chain=forward action=mark-packet new-packet-mark=test
Now the first packet of a connection gets compared five times, and a connection mark is set. Every subsequent packet, whether it's part of the connection or not, is only compared two times: is this a new connection? No. Does it have this connection mark? Yes.
Both packet marks and connection marks are internal to the router only. They are not ever transmitted on the wire, and the next router that sees the traffic has no idea the packet or connection were ever marked.
Simple queues can work without packet marks, but you can use them if you want to. For queue trees it usually doesn't make sense to not use packet marks.
Hope that helps.